Сортировка выбором 2
A[1..N] - сортируемый массив из n элементов.
for ( i=1; i<N; i++)
Hайти наименьший из элементов i..N и поменять его местами с i-м.
Пример действий для случайного массива A[1..8]
44 55 12 42 94 18 06 67 исходный массив
i=1 06| 55 12 42 94 18 44 67 06 <-> 44
i=2 06 12| 55 42 94 18 44 67 12 <-> 55
i=3 06 12 18| 42 94 55 44 67 18 <-> 55
i=4 06 12 18 42| 94 55 44 67 42 <-> 42
i=5 06 12 18 42 44| 55 94 67 44 <-> 94
i=6 06 12 18 42 44 55| 94 67 55 <-> 55
i=7 06 12 18 42 44 55 67| 94 67 <-> 94
Вертикальной чертой отмечена граница уже отсортированной части
массива.
Сортировка выбором - простейший алгоритм, на практике не
используемый ввиду низкого быстродействия. Вместо этого
применяют ее улучшение - пирамидальную сортировку (Heapsort),
описанную в другом вопросе, а также (иногда) 'древесную сортировку'
(TreeSort).
Пример на Паскале - Hиколас Вирт.
--------------------------------------------------------------------
{ Сортируются записи типа item по ключу item.key }
{ для вспомогательных переменных используется тип index }
procedure SelectSort;
var i, j, k: index; x:item;
begin for i:=1 to n-1 do
begin k:=i; x:=a[i];
for j:=i+1 to n do
if a[j].key < x.key then
begin k:=j; x:=a[j];
end;
a[k]:=a[i]; a[i]:=x;
end;
end;
|