Знайте, Intuit, лекция, сортиране масиви

сортиране задача

Тази лекция е посветена на чисто алгоритмичен поръчване данни проблем.

Необходимостта да сортирате всяка величина се случва в програмирането много често. Например, въвеждане на данни, се предоставя "смесен", а програмата ви е по-удобно да се справя подредена последователност. Има ситуации, в които предварително сортиране на данни може да намали значителна част от алгоритъма на моменти и по време на изпълнението - в десетки пъти.

Въпреки това, обратното е вярно. Без значение колко добър и ефективен, без значение от избрания алгоритъм. но ако той използва подзадачи като "лош" сортиране цялата работа по оптимизирането й е безполезна. Слабо приложени сортиране на входни данни може значително да намали ефективността на алгоритъма като цяло.

методи за поръчка са разделени на вътрешния (за обработка на масиви) и външната (занимаващи се с файлове) 1 За повече информация за различните поръчки алгоритми, вижте книгата на Доналд Кнут е "Изкуството на компютърното програмиране", том 3, "сортиране и търсене."

Тази лекция ще бъде посветена само на вътрешния сортирането. Тяхната важна характеристика е, че тези алгоритми не се нуждаят от допълнителна памет: цялата работа да се рационализира, произведени в рамките на същия масив.

прост сортиране

С прости методи на вътрешните сортиране включват сложността на която е пропорционална на квадрата на измерение на входните данни. С други думи, в масив сортиране. състоящ се от N компоненти. Такива алгоритми ще бъдат проведени * N 2 действие, където С - константа.

Броят на необходимите действия за поръчване на поредица от данни, разбира се, не зависи само от дължината на последователност, но и на неговата структура. Например, ако на входа вече е подредена последователност (каква програма. Това е разбираемо, не знам), броят на операциите ще бъде много по-малък, отколкото в случай на смесени вход.

Обикновено, сложността на алгоритмите се броят отделно за броя на сравненията, а броят на движение на данни в съхранение (трансфери), тъй като тези операции различно време. Въпреки това, точните стойности рядко са в състояние да се намери, така че за алгоритмите за оценка са ограничени до термина "пропорционално", което не се вземат предвид конкретните стойности на константите в крайна формула. Общата ефективност на алгоритъма обикновено се оценява "средно": средната аритметична стойност на сложността на алгоритъма "в най-добрия" и "най-лошото", т.е. (+ Eff_best Eff_worst) / 2.

Сортиране само чрез вмъкване

Най-лесният начин да се справи 2 Имената на алгоритмите ние следваме Кнут. което идва на ум - това подреждане на данни, тъй като те станат достъпни. В този случай, при въвеждане на всяка нова стойност може да се основава на факта, че всички предишни елементи вече формират подредени последователност.

1. Първият елемент да пише "без колебание".
2. До края на последователността на въвеждане на данните за всеки нов компонент от него за изпълнение на следните стъпки:

- считано от края на съществуваща подреден последователност, всички негови елементи, които са по-големи от нововъведената елемент да се движат една стъпка назад;

- запишете нов елемент за място.

В същото време, разбира се, можете да прочетете всички входни елементи в същото време, да ги напиша в масив, а след това "да си представите", че всеки следващ елемент е въведена точно това. На характера и структурата на алгоритъма не е засегната.

Изпълнението на PrVst на алгоритъм