Бинго-сортировка
Развитие сортировки выбором.
На каждом проходе будем находить не только очередной максимум но и максимум для следующего прохода. Это позволяет существенно экономить на сортировке массивов с повторяющимися значениями.
type TAI = array of integer; ... procedure BingoSort(var A: TAI); var maxI : integer; maxValue, nextvalue : integer; i : integer; begin maxI := High(A); nextValue := A[maxI]; for i := maxI-1 downto 0 do if A[i] > nextValue then nextValue := A[i]; while (maxI>0) and (A[maxI] = nextValue) do dec(maxI); while maxI > 0 do begin maxValue := nextValue; nextValue := A[maxI]; for i := MaxI - 1 downto 0 do begin if A[i] = maxValue then begin swap(A[i], A[maxI]); dec(maxI); end else if A[i] > nextValue then nextValue := A[i]; end; while (maxI>0) and (A[maxI] = nextValue) do dec(maxI); end; end;
Максимальная | O(N2) |
Минимальная | O(N2) |
Средняя | O(N2) |
Метки: