如何在雙鏈表的指針上實現快速排序？

Question

我有用於快速排列指針數組的代碼（如果可以幫助任何人），但我如何做一個doble鏈接指針列表？

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。只要你需要隨機訪問一個元素，你需要遍歷你的列表。顯然這會破壞業績。很多Quicksort算法不需要隨機訪問。以Inc和Dec語句爲例的算法的那些部分對於列表而言是微不足道的。但問題是主要選擇。在你上面的代碼是這一行：

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

雖然你可以清楚的實現，對於一個列表，它是低效的。

對於鏈表，搜索算法的有效選擇是Mergesort。從維基百科頁面的摘錄說：

歸併排序是經常進行排序鏈表的最佳選擇：在這種情況下，它是相對容易以這樣的方式來實現合併排序，它僅需要Θ（1 ）額外的空間，並且鏈表的緩慢的隨機訪問性能使得一些其他算法（例如快速排序）表現不佳，而其他算法（例如堆排序）完全不可能。