Сортировка вставками с бинарным поиском
Усовершенствование сортировки простыми вставками, в которой для поиска места вставки используектся бинарный поиск.
type TAI = array of integer; ... procedure InsertionWithBSearchSort(var A: TAI); var i, j: integer; left, right, mid: integer; value: integer; begin for i := Low(A)+1 to High(A) do begin left := Low(A); right := i; while left<right do begin mid := (left+right) div 2; if A[i]<A[mid] then right := mid else left := mid + 1; end; value := A[i]; for j := i-1 downto left do A[j+1] := A[j]; A[left] := value; end; end;
Максимальная | O(N(log(N)) |
Минимальная | O(N(log(N)) |
Средняя | O(N(log(N)) |
Метки:
- Войдите или зарегистрируйтесь, чтобы отправлять комментарии