delphi - 如何在指针的双链表上实现快速排序？

Question

我有用于快速排序指针数组的代码(如果对任何人有帮助)，但是我如何对指针的双链表进行快速排序？

procedure TSuperList.Sort;
begin
 if Assigned(FOnCompare) and (Length(Items)>1) then
  QuickSort(0,High(Items));
end;

procedure TSuperList.QuickSort(L,R:Integer);
var I,J: Integer;
    P,T: Pointer;
begin
  repeat
    I:=L;
    J:=R;
    P:=Items[(L+R) shr 1];
    repeat
      while FOnCompare(self,Items[I],P) < 0 do Inc(I);
      while FOnCompare(self,Items[J],P) > 0 do Dec(J);
      if I <= J then begin
        if I <> J then begin
          T:=Items[I]; Items[I]:=Items[J]; Items[J]:=T;
        end;
        Inc(I);
        Dec(J);
      end;
    until I > J;
    if L < J then QuickSort(L,J);
    L:=I;
  until I >= R;
end;

Answer 1

当您可以使用 O(1) 随机访问时，快速排序是一个不错的选择。否则这不是一个好的选择。

您当然可以使用双向链表实现快速排序。只是每当您需要随机访问某个元素时，您都需要单步浏览列表。显然这会破坏性能。许多快速排序算法不需要随机访问。以 Inc 和 Dec 语句为例的算法部分对于列表来说是微不足道的。但问题是支点选择。在上面的代码中是这一行:

P:=Items[(L+R) shr 1];

虽然您可以清楚地为列表实现这一点，但效率很低。

对于链表，搜索算法的有效选择是 Mergesort 。维基百科页面的摘录如下:

Merge sort is often the best choice for sorting a linked list: in this situation it is relatively easy to implement a merge sort in such a way that it requires only Θ(1) extra space, and the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.