Здравствуйте, Dimon4ik.
Создал код на базе Вашего. Постарался прокомментировать.
Если комментариев недостаточно, спрашивайте.
Компилятор Borland C++ 3.1

Приложение:
#include <stdlib.h>
#include <conio.h>
#include <iostream.h>
#include <dos.h> // Т. к. функции time.h дают время с точностью до 1 секунды
//используем функции dos.h, которые дают время с точностью до 0.01 секунды.

long my_get_time ()
{
struct time t;
gettime(&t);
return(t.ti_hund+100*(t.ti_sec+60*(t.ti_min+24*t.ti_hour)));// Время с начала дня в сотых секунды
}

void main()
{
int a[10000];// Увеличен предельный размер массива, т. к. даже такая медленная сортировка
// для тысячи элементов даёт время сортровки менее 1 сотой секунды.
int i,n,j,key,c, min,tmp;
long start, stop;
clrscr();

cout << "Kol-vo elementov = ";
cin >> n;
for (i=0;i<n;i++)
a[i]=random(30000);// Этот код вставлен вместо Вашего, закомменированного ниже, чтобы не вводить 1000 чисел ручками
//{
// cout <<"\nA[" <<i<<"]=";
// cin >> a[i];
//}

//cout << "______________________________";
//cout << "\nProverka";
//for (i=0;i<n;i++)
//{
// cout<< " " << a[i];
//}

// К сожалению, Ваша сортировка не работает. Её тоже закомментируем.

//for (i=0;i<n;i++)
//{
//key=a[i];
//j=i-1;
//while (j>=0 &key<a[j])
//{
// a[j+1]=a[j];
// j--;
//}
//a[j+1]=key;
//}

//Простейшая сортировка выбором:
start=my_get_time();
for(i=0;i<n-1;i++)
{
min=i; //предположим что самый первый из неупорядоченных пока эл-тов массива - минимальный
for(j=i+1;j<n;j++)//Пробегаем по остальным элементам массива
if(a[j]<a[min]) // Если найден эл-т меньше текущего минимума, назначаем его текущим минимальным
min=j;

tmp=a[min];//обмениваем первый из неупорядоченных пока эл-тов массива
a[min]=a[i];// с найденным минимумом
a[i]=tmp;//т. е. гарантировано, что элементы с нулевого по i-й уже упорядочены
}
stop=my_get_time();
cout << "\n_______________________________";
cout <<"\nOtsortirovano:";
for (i=0;i<n;i++)
cout << "\n" <<a[i];
cout << "\nProshlo vremeni: ";
cout << stop-start << " sotyh sek";
getch();
}