C# QuickSort 太慢

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

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

Answer 1

排序的速度以及应该使用的算法在很大程度上取决于输入数据。它是随机的、接近排序的、反转的等等。

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

• Sorting Algorithm Animations