Глава 1 (продолжение )
На первом шаге выполняется сортировка первых двух элементов массива.
Далее алгоритм ставит третий элемент в порядковую позицию,соответствующую
его положению относительно первых двух элементов.Затем в этот список вставляется четвертый элемент и тд.
Алгоритм сортировки методом вставки обладает двумя реальными
преимуществами.Во первых его поведение естественно.
Это означает,что если массив уже отсортирован в нужном порядке,
алгоритм проводит наименьшее количество вычислений,а если
массив отсортирован в порядке обратном требуемому(наихудший случай),
-его работа наиболее интенсивна.(по сравнению с предыдущими методами).
Другим преимуществом является то,что этот метод не изменяет порядка
следования одинаковых ключей.Это означает,что если массив уже
отсортирован по двум ключам,то после сортировки методом вставки
он остается отсортирован по обоим ключам.
При каждой вставке элемента на его место,должен выполняться
сдвиг массива!В результате количество перестановок может оказаться
довольно значительным.
//параметризованная версия сортироки методом вставки
#include <iostream.h>
#include <string.h>
template <class Stype> void insert(Stype *item,int count);
main()
{
//сортировка массива символов
char str[] = "dcab";
insert(str, (int) strlen(str));
cout<<"Otsortirovannyi massiv simvolov- " << str << endl;
char enterchar;
cout<<endl<<endl<<"Type any character to finish:";
cin>>enterchar;
//сортировка массивов целых чисел
int nums[] = {
5,7,3,9,5,1,8};
int i;
insert(nums,7);
cout<<" Otsortirovannyi massiv chisel : ";
for(i=0;i<7;i++) cout <<nums[i] <<" ";
//char enterchar;
cout<<endl<<endl<<"Type any character to finish:";
cin>>enterchar;
return 0;
}
//параметризованная функция сортировки отбором
template <class Stype> void insert(Stype *item,int count)
{
register int a,b;
Stype t;
for(a=1;a<count;++a)
{
t = item[a];
for(b=a-1;b>=0 && t<item[b];b--)
{
item[b+1] = item[b];
}
item[b+1] = t;
}
}
Результат:
Otsortirovannyi massiv simvolov- abcd
Otsortirovannyi massiv chisel : 1 3 5 5 7 8 9
Наконец то результат правильный!
Назад |
Начало урока |
Вверх |
Вперед
Содержание