我有用于对指针数组进行快速排序的代码(如果有帮助的话),但是我如何针对一个可疑的指针列表呢?
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算法不需要随机访问。对于列表,用Inc
和Dec
语句例示的算法的那些部分微不足道。但是问题是关键选择。在上面的代码中,该行是:
P:=Items[(L+R) shr 1];
尽管您可以为列表清楚地实现它,但是效率很低。
对于链表,搜索算法的有效选择是Mergesort。该维基百科页面的摘录说:
合并排序通常是对链表进行排序的最佳选择:在这种情况下,以仅需Θ(1)额外空间以及链表随机访问性能较慢的方式实现合并排序相对容易list使得其他一些算法(例如quicksort)的性能较差,而其他算法(例如堆排序)则完全不可能。