![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Простая вставка
Алгоритм сортировки простыми вставками производится в цикле j=2, 3,..., N. На начальном этапе упорядоченная последовательность состоит их одного элемента X1. На j-м этапе запись Х(J) вставляется на свое правильное место среди Х(1), Х(2),..., Х(j-1). При вставке запись Х(j) временно размещается в запись S и просматриваются записи Х(j-1), Х(j-2),..., Х(1); их ключи сравниваются с ключом T записи S и записи сдвигаются вправо, если обнаруживается, что их ключи больше Т. Структурограмма алгоритма сортировки методом вставки представлена на рис.
Пример. 5, 4, 1, 2, 3 J=2, I=1, T=4 5 5 1 2 3 I=0 4 5 1 2 3 J=3, I=2, T=1 4 5 5 2 3 I=1 4 4 5 2 3 I=0 1 4 5 2 3 J=4, I=3, T=2 1 4 5 5 3 I=2 1 4 4 5 3 I=1 1 4 4 5 3 1 2 4 5 3 J=5, I=4, T=3 1 2 4 5 5 I=3 1 2 4 4 5 I=2 1 2 3 4 5
Пример реализации: procedure SortInsert (var Arr: array of Integer; n: Integer); var i, j, Temp: Integer; begin for i: = 1 to n do begin Temp: = Arr [i]; j: = i - 1; while Temp < Arr [j] do begin Arr [j + 1]: = Arr [j]; Dec (j); if j < 0 then Break; end; Arr [j + 1]: = Temp; end; end;
Характеристики метода вставки: 1. Наиболее эффективен для частично отсортированных записей. 2. Число сравнений: - минимальное – N-1; - максимальное - N*(N-1)/2. 3. Число перемещений: - минимальное – 0; - максимальное - N*(N-1)/2. 4. Не требуется наличие всего набора данных до начала сортировки
|