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

Delphi

Сортировка слиянием

Чтобы объединить два отсортированных массива в один, можно сравнивать два их крайних элемента и наиболее подходящий извлекать в результат. Таким образом мы сольём источники в массив, который останется сортированным.

Если исходный массив разделить на две половинки, которые окажутся отсортированными, то как поступать дальше - понятно.

Чтобы получить сортированные половинки, достаточно применить к ним сортировку слиянием... 

Таким образом: рекурсивно разделяем сортируемую область на две, сортируем их по отдельности и затем сливаем обратно.

type
  TAI = array of integer;
...
procedure MergeSort(var A: TAI);
var
    T: TAI; // Временный массив для слияний.

  // Слияние двух областей (L1-L2) и (R1-R2), идущих подряд.
  procedure merge(L1,L2,R1,R2: integer);
  var
      i: integer;
  begin
    i:=0;
    repeat
      // Забираем подходящее из левого диапазона.
      while (L1 <= L2) and ((R1>R2) or (A[L1]<=A[R1])) do
      begin
        T[i] := A[L1];
        inc(i);
        inc(L1);
      end;
      // Забираем подходящее из правого диапазона. 
      while (R1 <= R2) and ((L1>L2) or (A[L1]>=A[R1])) do
      begin
        T[i] := A[R1];
        inc(i);
        inc(R1);
      end;
    until (L1>L2) and (R1>R2); // пока оба источника не закончатся.
    // Возвращаем результат в исходный массив.
    L1 := R1 - i;
    dec(i);
    while i>=0 do
    begin
      A[i+L1] := T[i];
      dec(i);
    end;
  end;

  // Сортировка диапазона от l до r
  procedure msort(l, r : integer);
  var
    m : integer;
  begin
    // если в диапазоне меньше трёх элементов,
    if (r-l)<2 then
    begin
      // сортировка тривиальна.
      if A[l]>A[r] then swap(A[l],A[r]);
    end
      else // Если больше:
    begin
      // найдём середину,
      m := (l+r) div 2;
      // отсортируем левую часть,
      msort(l, m);
      // отсортируем правую часть,
      msort(m+1, r);
      // сольём отсортированные массивы.
      merge(l,m,m+1,r);
    end;
  end;

begin
  // Подготавливаем временный массив.
  SetLength(T, length(A));
  // Запускаем сортировку.
  msort(Low(A), High(A));
end;

Сложность:

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

 

Filtered HTML

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

Plain text

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