我有用于对指针数组进行快速排序的代码(如果有帮助的话),但是我如何针对一个可疑的指针列表呢?

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;

最佳答案

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

当然,您可以使用双向链表实现Quicksort。只是只要您需要随机访问某个元素,就需要逐步浏览列表。显然,这将破坏性能。许多Quicksort算法不需要随机访问。对于列表,用IncDec语句例示的算法的那些部分微不足道。但是问题是关键选择。在上面的代码中,该行是:

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


尽管您可以为列表清楚地实现它,但是效率很低。

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


合并排序通常是对链表进行排序的最佳选择:在这种情况下,以仅需Θ(1)额外空间以及链表随机访问性能较慢的方式实现合并排序相对容易list使得其他一些算法(例如quicksort)的性能较差,而其他算法(例如堆排序)则完全不可能。

10-05 20:43
查看更多