КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Сортировка простым выборомСортировка подсчетом Внутренняя сортировка Различают внутреннюю и внешнюю сортировку. Под внутренней сортировкой понимают сортировку в условиях, когда вся таблица помещается в оперативную память. Внешняя сортировка – это сортировка данных на внешнем носителе, причем доступный объем оперативной памяти недостаточен для того, что считать сразу всю таблицу в оперативную память. Этот простой метод основан на том, что j -й ключ в сортированной последовательности превышает ровно j-1 ключ. В первой фазе алгоритм подсчитывает для каждого ключа число ключей, которые меньше его. Значение счетчика для ключа и есть тот номер позиции в сортированной таблице, который он должен занять. void CountSort(int n, int t[]){ // t – сортируемый массив целых чисел длиной n int i,j; int *c=new int[n]; // массив счетчиков // обнулим счетчики for(i=0; i<n; i++) c[i]=0; // фаза подсчета for(i=0; i<n; i+){ for(j=0; j<i; j++){ if(t[i]>t[j]){ c[i]++; } else { c[j]++; } } } // фаза расстановки for(i=0; i<n; i++){ while(i!=c[i]){ // до тех пор, пока t[i] не займет // окончательного положения swap(t[i],t[c[i]]); // обмен местами эл-тов таблицы swap(c[i],c[c[i]]); // обмен местами счетчиков } } } Ключ ti в исходной последовательности сравнивается с i предшествующими ключами и, следовательно, общее число сравнений равно то есть пропорционально N2. Просматривая исходную последовательность ключей t, начиная с t0, находим среди них наименьший и меняем местами с t0, затем повторяем процесс начиная с t1, находим наименьший и меняем местами с t1, и так далее до конца таблицы. Ниже представлен текст функции, выполняющей сортировку простым выбором. void SimpleChoice(int n, int t[]){ int i,j,k; for(i=0; i<n; i++){ k=i; // к моменту завершения цикла по j, k будет индексом // наименьшего ключа на отрезке i…N-1 for(j=i+1;j<n;j++){ if(t[j]<t[k]){ k=j; } } swap(t[i], t[k]); } } В этом случае время также пропорционально N2, так как при поиске наименьшего ключа на отрезке i…N-1, потребуется выполнить N-i-1 сравнений. Суммируя по i, получим величину, пропорциональную N2.
Дата добавления: 2014-12-08; Просмотров: 462; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |