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

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) 随机访问时，Quicksort 是一个不错的选择。否则这不是一个好的选择。

你当然可以用你的双向链表实现快速排序。只是任何时候你需要随机访问一个元素，你都需要遍历你的列表。显然，这会破坏性能。许多快速排序算法不需要随机访问。由 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.

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

How to implement quicksort on a double-linked list of pointers?

delphi

pointers

quicksort

delphi-2009