为什么我的链表快速排序比数组慢很多？

Question

我是算法题，需要我实现链表和数组的快速排序算法。
我已经完成了这两个部分，算法正在运行，但我的快速排序链表实现似乎存在一些错误。

这是我的快速排序链表实现。

public static void SortLinkedList(DataList items, DataList.Node low, DataList.Node high) 
    {
        if( low != null && low !=high)
        {
            DataList.Node p = _PartitionLinkedList(items, low, high);
            SortLinkedList(items, low, p);
            SortLinkedList(items, p.Next(), null);
        }


    }

    private static DataList.Node _PartitionLinkedList(DataList items, DataList.Node low, DataList.Node high) 
    {
        DataList.Node pivot = low;
        DataList.Node i = low;
        for (DataList.Node j = i.Next(); j != high; j=j.Next())
        {
            if (j.Value().CompareTo(pivot.Value()) <= 0)
            {

                items.Swap(i.Next(),j);
                i = i.Next();

            }
        }
        items.Swap(pivot, i);
        return i;
    }

这是快速排序数组的实现

 public static void SortData(DataArray items, int low, int high) 
    {
        if (low < high)
        {
            int pi = _PartitionData(items, low, high);
            SortData(items, low, pi - 1);
            SortData(items, pi + 1, high);
        }

    }
 static int _PartitionData(DataArray arr, int low, int high) 
    {
        double pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j <= high - 1; j++)
        {
            if (arr[j].CompareTo(pivot)<=0)
            {
                i++;
                arr.Swap(i,j);
            }
        }
        arr.Swap(i + 1, high);
        return i + 1;
    }

这是快速排序数组和链表的表现。 (左边n，右边时间)
Picture
如您所见，qs 链表需要 10 分钟才能对 6400 个元素进行排序。我认为这不正常..

我也不认为这是因为数据结构，因为我使用相同的结构进行选择排序并且链表和数组的性能相似。

GitHub 回购以防我忘记提供一些代码。 Repo

Answer 1

我会看看你的链表，尤其是交换方法。除非我们看到链表的实现，否则我认为问题所在。

您使用链表有什么原因吗？他们有 o(n) 搜索，使快速排序 n^2lg(n) 排序。

另一种方法是将链接列表中的所有项目添加到列表中，对该列表进行排序，然后重新创建链接列表。 List.Sort() 使用快速排序。

public static void SortLinkedList(DataList items) 
{
    list<object> actualList = new list<object>();

    for (DataList.Node j = i.Next(); j != null; j=j.Next())
    {
        list.add(j.Value());
    }

    actualList.Sort();

    items.Clear();
    for (int i = 0; i < actualList.Count;i++)
    {
        items.Add(actualList[i]);
    }
}

Answer 2

10 分钟对于 6400 个元素来说是一个非常长的时间。它通常需要 2 或 3 个可怕的错误，而不仅仅是一个。

不幸的是，我只看到一个可怕的错误：您对 SortLinkedList(items, p.Next(), null); 的第二次递归调用一直到列表的末尾。你的意思是让它停在 high.

这可能占了 10 分钟，但似乎不太可能。

在我看来你的排序也不正确，即使你修复了上述错误 -- 请务必测试输出！

Answer 3

链表的快速排序通常与数组的快速排序略有不同。使用第一个节点的数据值作为枢轴值。然后代码创建了 3 个列表，一个用于 values < pivot，一个用于 values == pivot，一个用于 values > pivot。然后它对 < pivot 和 > pivot 列表进行递归调用。当递归调用 returns 时，这 3 个列表现在已排序，因此代码只需要连接这 3 个列表。

要加快列表的连接速度，请跟踪指向最后一个节点的指针。为了简化这一点，使用循环列表，并使用指向最后一个节点的指针作为访问列表的主要方式。这使得附加（加入）列表更简单（无需扫描）。一旦进入函数，使用 last->next 以获得指向列表第一个节点的指针。

两种最坏情况的数据模式是已经排序的数据或已经反向排序的数据。如果使用指向最后一个节点方法的循环列表，那么最后一个节点和第一个节点的平均值可以用作 2 的中位数，这可能会有所帮助（注意节点列表 == pivot 可能最终为空）。

最坏情况下的时间复杂度为 O(n^2)。最坏情况下的堆栈使用是 O(n)。通过对列表 < pivot 和 list > pivot 中较小的一个使用递归，可以减少堆栈的使用。在 return 之后，现在排序的较小列表将与列表 == pivot 连接并保存在第 4 个列表中。然后排序过程将迭代剩余的未排序列表，然后与保存的列表合并（或可能加入）。

使用任何方法（包括 bottom up merge sort ）对链表进行排序，比将链表移动到数组、对数组排序，然后从排序后的数组创建链表要慢。然而，我描述的快速排序方法将比使用带有链表的面向数组的算法快得多。

为什么我的链表快速排序比数组慢很多？

Why my implementation of linked list quick sort is much slower than array one?

c#

sorting

algorithm

list

quicksort