![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Cортировка Шелла (ShellSort)Стр 1 из 2Следующая ⇒
Билет №11 Сортировка. Классификация алгоритмов сортировки. Сортировка – это расстановка элементов массива в заданном порядке (по возрастанию, убыванию, последней цифре, сумме делителей, …). Сортировки бывают следующих видов: 1) Обменные: Пузырьком, перемешиванием, гномья, быстрая. Расческой, сортировка чет-нечет 2) Выбором: выбором, пирамидальная, плавная 3) Вставками: вставками, Шелла, деревом 4) Слиянием 5) Без сравнений: подсчетом, поразрядная, блочная 6) Гибридные: Introsort, Timsort Алгоритмы: 1) простые и понятные, но неэффективные для больших массивов(сложность O(N2)) · метод пузырька · метод выбора 2) сложные, но эффективные(сложность O(N· log N)) · " быстрая сортировка" (Quick Sort) · сортировка " кучей" (Heap Sort) · сортировка слиянием · пирамидальная сортировка Квадратичные и субквадратичные алгоритмы Сортировка выбором(SelectSort) Найти минимальный элемент и поставить на первое место (поменять местами с A[0]). Из оставшихся найти минимальный элемент и поставить на второе место (поменять местами с A[1]), и т.д. Пример: for (i = 0; i< N-2; i++) {nMin = i; for (j= i+1; j< N; j++) if (A[j] < A[nMin]) nMin: =j; if (nMin! = i) { c=A[i]; A[i]=A[nMin]; A[nMin]=c; } } Сортировка пузырьком(BubbleSort) Самый маленький (" легкий") элемент перемещается вверх (" всплывает"). Начиная снизу, сравниваем два соседних элемента; если они стоят " неправильно", меняем их местами. За 1 проход по массиву один элемент (самый маленький) становится на свое место. Для сортировки массива из N элементов нужен Пример: for (i=0; i< N-1; i++) for (j=N-2; j< = i; j--) if (A[j] > A[j+1]) {с: = A[j]; A[j]: = A[j+1]; A[j+1]: = с; } Условие Айверсона(Флаг): Идея– если при выполнении метода пузырька не было обменов, массив уже отсортирован и остальные проходы не нужны. Реализация: переменная-флаг, показывающая, был ли обмен; если она равна False, то выход. Пример: i = 0; do {flag = 0; // сбросить флаг for (j=N-1; j > = 0; j--) if (A[j] > A[j+1]) { с = A[j]; A[j] = A[j+1]; A[j+1] = с; flag = 1; // поднять флаг } i = i + 1; } while flag; //продолжать пока флаг поднят
3) Сортировка простыми вставками (InsertSort) (в презентации примера нет) Cортировка Шелла (ShellSort) Работает с элементами отстоящими друг от друга на расстоянии d Сначала d=[n/2]. На следующих проходах d меняется по закону d=[d/2].
|