3

我现在正在学习不同类型的排序，我发现从某个点开始，我的 QuickSort 算法根本没有那么快。

这是我的代码：

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 在不到一秒的时间内完成相同的操作。

你能向我解释为什么会发生这种情况吗？

4

3 回答 3

4

您的排序速度以及您应该使用哪种算法取决于您的大量输入数据。它是随机的，几乎排序的，反转的等。

有一个很好的页面说明了不同的排序算法是如何工作的：

于 2011-01-20T11:53:24.993 回答
2

您是否考虑过内联该Swap方法？这样做应该不难，但可能是 JIT 发现很难内联。

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

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

于 2011-01-20T11:54:04.233 回答
1

您有 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 次 1,000 + 999 + 998 + ... + 1 次比较。（在每一轮快速排序将问题减少一个，只删除键/枢轴。）这给出了 500,000,000 次操作。对 1,000 个分区进行快速排序的最理想方式是 1,000 次 1,000*10 次操作 = 10,000,000。由于相同的值，您在这里遇到了二次情况，即快速排序的最坏情况性能。所以，大约在快速排序的一半，它会出现最坏的情况。

如果每个值只出现几次，那么将这些小分区排序到O(N^2)or中并不重要O(N logN)。但是在这里我们有很多很大的分区要分类O(N^2)。

改进您的代码：分成 3 部分。小于枢轴，等于枢轴，大于枢轴。然后，只对第一个和最后一个分区进行快速排序。你需要做一个额外的比较；首先测试是否相等。但我认为，对于这个输入，它会快很多。

于 2011-02-07T12:21:24.740 回答