48

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

4

6 回答 6

63

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

然而，快速排序的最坏情况性能明显低于堆排序。因为一些关键应用程序需要保证速度性能，所以堆排序是处理这种情况的正确方法。

于 2009-12-05T19:41:39.427 回答
22

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

我自己测试了算法，我发现 Quicksort 确实有一些特别之处。它运行得很快，比堆和合并算法快得多。

Quicksort 的秘诀在于：它几乎不会进行不必要的元素交换。交换很费时间。

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

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

使用快速排序，您不会交换已订购的内容。如果您的数据是完全有序的，那么您几乎不需要交换任何东西！虽然对于最坏的情况有很多大惊小怪，但在选择枢轴上稍作改进，除了获取数组的第一个或最后一个元素之外，可以避免它。如果您从第一个、最后一个和中间元素之间的中间元素获得一个枢轴，则足以避免最坏的情况。

快速排序的优势不是最坏的情况，而是最好的情况！在最好的情况下，您进行相同数量的比较，好吧，但您几乎没有交换任何内容。在一般情况下，您交换部分元素，但不是所有元素，如堆排序和合并排序。这就是为快速排序提供最佳时间的原因。更少的交换，更快的速度。

下面的 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);
}
于 2015-02-15T04:05:33.780 回答
8

这里有几个解释：

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

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

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

于 2009-12-05T19:40:46.183 回答
1

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

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

于 2010-07-31T13:29:39.660 回答
0

平均情况复杂性，以及您可以采取简单的步骤来最小化快速排序中最坏情况复杂性的风险这一事实（例如，选择枢轴作为三个元素的中位数而不是单个选定位置）。

于 2009-12-05T19:40:50.513 回答
0

如前所述，与堆排序相比，快速排序具有更好的参考局部性，但最坏的情况具有 O(n^2) 复杂度。

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

于 2021-01-06T16:10:25.677 回答