C#快速排序太慢了

Question

我现在正在学习不同类型的排序，发现从某一点开始，我的快速排序算法根本就不那么快了。

以下是我的代码：

class QuickSort
    {

       // partitioning array on the key so that the left part is <=key, right part > key
            private int Partition(int[] arr, int start, int end)
            {
                    int key = arr[end];
                    int i = start - 1;
                    for (int j = start; j < end; j++)
                    {
                            if (arr[j] <= key) Swap(ref arr[++i], ref arr[j]);
                    }
                    Swap(ref arr[++i], ref arr[end]);
                    return i;
            }


            // sorting
            public void QuickSorting(int[] arr, int start, int end)
            {
                    if (start < end)
                    {
                            int key = Partition(arr, start, end);
                            QuickSorting(arr, start, key - 1);
                            QuickSorting(arr, key + 1, end);
                    }
            }
      }


    class Test
    {
            static void Main(string[] args)
            {                       
                    QuickSort quick = new QuickSort();
                    Random rnd = new Random(DateTime.Now.Millisecond);

                    int[] array = new int[1000000];

                    for (int i = 0; i < 1000000; i++)
                    {
                            int i_rnd = rnd.Next(1, 1000);
                            array[i] = i_rnd;
                    }

                    quick.QuickSorting(array, 0, array.Length - 1);

            }
      }

在一个包含一百万个元素的数组上运行这段代码大约需要15秒的时间。而例如MergeSort或HeapSort则可以在不到一秒钟的时间内完成相同的任务。

您能否解释一下为什么会出现这种情况？

- mau6

---

尝试将数字值的范围从1000增加到10000000，我认为问题在于您对值进行了太多次洗牌。 - Lasse V. Karlsen

很有趣，你说得完全正确！我把数字增加到1000000，现在快速排序真的很快。谢谢。 - mau6

一个O(1/n)算法就像是一个永动机。你选择了最糟糕的枢轴点。 - Hans Passant

由于近似二次行为，较小范围的结果变得更糟。如果您使所有元素相同，则确实会获得二次行为。查看 Bentley-McIlroy 分区以处理重复元素。@Hans：仅当数据未随机化时（如 OP 代码中）才是错误的枢轴选择。 - Justin Peel

Answer 1

你的排序速度和应该使用哪种算法，很大程度上取决于你的输入数据。它是随机的、几乎排序的、反转的等等。

有一个非常好的页面可以说明不同的排序算法如何工作:

• 排序算法动画

- Martin Buberl

---

数据是随机的，我甚至尝试了在排序时选择关键元素的随机版本，但它并没有产生任何变化。感谢提供链接！ - mau6

Answer 2

您是否考虑内联Swap方法？这应该不难做到，但可能是JIT在内联方面遇到了困难。

当我为Edulinq实现快速排序时，我根本没有看到这个问题 - 您可以尝试我的代码（可能是最简单的递归形式）来查看其性能如何。如果表现良好，请尝试找出差异所在。

虽然不同的算法会在相同的数据下表现不同，但我不希望在随机生成的数据上看到如此大的差异。

- Jon Skeet

---

它是否将ints装箱以便可以创建引用？几乎肯定是交换的问题。 - Rup

@Rup：不，这不会将ints装箱。 - Jon Skeet

谢谢，我会尝试你的代码。交换部分如下：private void Swap (ref int a, ref int b) { int temp = a; a = b; b = temp; } - mau6

你的代码运行速度提升了5倍，但我还在寻找原因。与此同时，如Lasse V. Karlsen所建议的，我将随机数的数量从1更改为1000000（而不是从1到1000），这真的有所帮助。 - mau6

Answer 3

你有1,000,000个包含1,000种不同值的随机元素。因此，我们可以期望大多数值在你的数组中出现大约1,000次。这会导致你的程序具有二次的O(n^2)运行时间。

将数组分成1,000个相等的片段，每个片段包含相同数量的元素时，需要大约log2(1000)或10个堆栈深度。（假设调用partition函数可以将数组整齐地分成两个部分）。这大约需要10,000,000次操作。

对最后1,000个包含1,000个相同值的分区进行快速排序，我们需要1,000 x 1,000 + 999 + 998 + ... + 1次比较。（每轮快速排序仅减少一个键/枢轴）。这会产生500,000,000次操作。最理想的快速排序1,000个分区的方法是1,000 x 1,000 x 10次操作= 10,000,000次。但由于存在相同的值，你会遇到一种二次的情况，即快速排序的最坏性能。因此，在快速排序进行到一半时，它会退化为最坏情况。

如果每个值只出现几次，那么将这些少量的分区按照 O(N^2) 或者 O(N logN) 进行排序并不重要。但是在这里，我们有很多且巨大的分区需要按照 O(N^2) 进行排序。

---

为了改进你的代码：将数据分成三个部分。小于枢轴的，等于枢轴的和大于枢轴的。然后，只对第一个和最后一个部分进行快速排序。你需要多做一次比较；首先测试相等性。但我认为对于这个输入来说会更快。

- Ishtar