Добавить комментарий

Delphi

Сортировка подсчётом

Создадим массив счётчиков для всех возможных значений в сортируемом массиве. За один проход подсчитаем количество вхождений каждого значения. Заполним результат подсчитанными значениями.

type
  TAI = array of integer;
...  
procedure CountingSort(var A: TAI);
var
    Counters : TAI;
    i,ii,j   : Integer;
    Min, Max : integer;
begin
  // Найдём границы диапазона.
  Min := High(A[0]);
  Max :=  Low(A[0]);
  for i:= Low(A) to High(A) do
  begin
    if A[i]>Max then Max := A[i];
    if A[i]<Min then Min := A[i];
  end;
  // Создаём счётчики.
  SetLength(Counters, Max-Min+1);
  // Считаем количество вхождений.
  for i:= Low(A) to High(A) do
  begin
    inc(Counters[A[i]-Min]);
  end;
  // Заполняем результат.
  j:=0;
  for i:= Low(Counters) to High(Counters) do
  begin
    for ii := 1 to Counters[i] do
    begin
      A[j] := i + Min;
      inc(j);
    end;
  end;
end;

По понятным причинам область самостоятельного применения этого алгоритма невелика.   

Не эффективно использовать его в случае, когда количество допустимых значений велико (например,   -2147483648..2147483647) или вовсе бесконечно (например, сортировка вещественных чисел).

Сложность:

Максимальная O(N)
Минимальная O(N)
Средняя O(N)

 

Filtered HTML

  • Адреса страниц и электронной почты автоматически преобразуются в ссылки.
  • Допустимые HTML-теги: <a> <em> <strong> <cite> <blockquote> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Строки и абзацы переносятся автоматически.
  • Вы можете цитировать другие сообщения, используя тэг [quote]

Plain text

  • HTML-теги не обрабатываются и показываются как обычный текст
  • Адреса страниц и электронной почты автоматически преобразуются в ссылки.
  • Строки и абзацы переносятся автоматически.