快速排序优于堆排序

Question

堆排序的最坏情况复杂度为 O(nlogn)，而快速排序的复杂度为 O(n^2)。 但经验证据表明快速排序更优越。这是为什么？

Answer 1

主要因素之一是快速排序具有更好的引用局部性——下一个要访问的内容通常在内存中与您刚刚查看的内容很接近。相比之下，堆排序的跳跃次数要多得多。由于靠近的事物可能会被缓存在一起，因此快速排序往往会更快。

然而，快速排序的最坏情况性能明显比堆排序差。由于某些关键应用程序需要保证速度性能，因此堆排序是处理此类情况的正确方法。

Answer 2

堆排序是 O(N log N) 保证的，这比快速排序中最坏的情况要好得多。堆排序不需要更多内存来容纳另一个数组来放置合并排序所需的有序数据。那么为什么商业应用程序坚持使用快速排序呢？与其他实现相比，快速排序有何特别之处？

我自己测试了这些算法，发现快速排序确实有一些特别之处。它运行速度很快，比Heap和Merge算法快得多。

快速排序的秘密是：它几乎不进行不必要的元素交换。交换很费时间。

使用堆排序，即使所有数据都已排序，您也将交换 100% 的元素来对数组进行排序。

如果使用合并排序，情况会更糟。您将把 100% 的元素写入另一个数组中，然后将其写回到原始数组中，即使数据已经排序。

使用快速排序，您不会交换已经订购的内容。如果你的数据是完全有序的，那么你几乎不需要交换任何东西！尽管对于最坏的情况有很多争论，但在主元的选择上稍加改进，除了获取数组的第一个或最后一个元素之外，都可以避免这种情况。如果从第一个、最后一个和中间元素之间的中间元素得到一个主元，就足以避免最坏的情况。

Quicksort的优越之处不是最坏的情况，而是最好的情况！在最好的情况下，你会进行相同数量的比较，好吧，但你几乎什么也不交换。一般情况下，您会交换部分元素，但不是全部元素，如堆排序和合并排序。这就是快速排序的最佳时机。更少的交换，更快的速度。

下面在我的计算机上用 C# 实现，在发布模式下运行，使用中间枢轴比 Array.Sort 快 3 秒，使用改进枢轴比 Array.Sort 快 2 秒（是的，获得良好枢轴需要一定的开销）。

static void Main(string[] args)
{
    int[] arrToSort = new int[100000000];
    var r = new Random();
    for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);

    Console.WriteLine("Press q to quick sort, s to Array.Sort");
    while (true)
    {
        var k = Console.ReadKey(true);
        if (k.KeyChar == 'q')
        {
            // quick sort
            Console.WriteLine("Beg quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            QuickSort(arrToSort, 0, arrToSort.Length - 1);
            Console.WriteLine("End quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);
        }
        else if (k.KeyChar == 's')
        {
            Console.WriteLine("Beg Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            Array.Sort(arrToSort);
            Console.WriteLine("End Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);
        }
    }
}

static public void QuickSort(int[] arr, int left, int right)
{
    int begin = left
        , end = right
        , pivot
        // get middle element pivot
        //= arr[(left + right) / 2]
        ;

    //improved pivot
    int middle = (left + right) / 2;
    int
        LM = arr[left].CompareTo(arr[middle])
        , MR = arr[middle].CompareTo(arr[right])
        , LR = arr[left].CompareTo(arr[right])
        ;
    if (-1 * LM == LR)
        pivot = arr[left];
    else
        if (MR == -1 * LR)
            pivot = arr[right];
        else
            pivot = arr[middle];
    do
    {
        while (arr[left] < pivot) left++;
        while (arr[right] > pivot) right--;

        if(left <= right)
        {
            int temp = arr[right];
            arr[right] = arr[left];
            arr[left] = temp;

            left++;
            right--;
        }
    } while (left <= right);

    if (left < end) QuickSort(arr, left, end);
    if (begin < right) QuickSort(arr, begin, right);
}

Answer 3

这里有一些解释：

http://www.cs.auckland.ac。 nz/software/AlgAnim/qsort3.html

http://users .aims.ac.za/~mackay/sorting/sorting.html

本质上，即使快速排序的最坏情况是 O(n^2)，它的平均性能也会更好。 :-)

Answer 4

大 O 表示法意味着对 n 个项目进行排序所需的时间受函数 c*n*log(n) 限制，其中 c 是一些未指定的常数因子。对于 quicksort 和 heapsort 来说，常量 c 没有理由应该相同。所以真正的问题是：为什么你会期望它们同样快？

在实践中，Quicksort 始终比 heapsort 快一些，但最近差异变得更大，因为如前所述，内存访问的局部性对于执行速度变得如此重要。

Answer 5

平均情况的复杂性，以及您可以采取简单的步骤来最大限度地降低快速排序中最坏情况复杂性的风险的事实（例如，选择主元作为三个元素的中位数，而不是单个选定位置）。

Answer 6

正如已经说过的，与堆排序相比，快速排序具有更好的引用局部性，但最坏情况的复杂度为 O(n^2)。

std::sort 是使用内省排序实现的：它大部分时间都运行快速排序，但在它检测到由于主元选择错误而导致运行时会很糟糕的情况下，它会切换到堆排序。在这种情况下，您将获得有保证的 O(nlog(n)) 复杂度以及几乎每次都会选择的快速排序的速度。