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

I have the code for quicksorting an array of pointers (if helps anyone) but how I do that for a doble linked list of pointers ?

我有快速分配指针数组的代码(如果帮助任何人)但我如何为一个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;

1 个解决方案

#1

Quicksort is a good choice when you can use O(1) random access. Otherwise it's a not a good choice.

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

You can certainly implement Quicksort with your doubly linked list. It's just that any time you need random access to an element, you need to step through your list. Clearly that is going to destroy performance. Much of the Quicksort algorithm does not need random access. Those parts of the algorithm exemplified by Inc and Dec statements are trivial for lists. But the problem is pivot choice. In your code above that is this line:

您当然可以使用双向链表实现Quicksort。只要您需要随机访问元素,就需要逐步浏览列表。显然这会破坏性能。大多数Quicksort算法不需要随机访问。以Inc和Dec语句为例的算法的那些部分对于列表来说是微不足道的。但问题是枢轴选择。在上面的代码中就是这一行:

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

Whilst you can clearly implement that for a list, it is inefficient.

虽然您可以清楚地将其用于列表,但效率很低。

For a linked list, the efficient choice of searching algorithm is Mergesort. An excerpt from that Wikipedia page says:

对于链表,搜索算法的有效选择是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.

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

#1