快速排序与堆排序

Question

快速排序和堆排序都是原地排序算法。哪个更好？在什么应用场景下，两者中的哪一个更受青睐？

- avd

---

可能是快速排序优于堆排序的重复问题。 - Bernhard Barker

Answer 1

堆排序的时间复杂度为O(N log N)，比快速排序最坏情况下的时间复杂度要好得多。堆排序不需要额外的数组来存储有序数据，因此比归并排序更省内存。那么为什么商业应用程序还是坚持使用快速排序？快速排序有什么特别之处，超过其他实现吗？

我亲自测试过算法，并且发现快速排序确实有一些特别之处。它运行速度快得多，比堆排序和归并排序都快。

快速排序的秘密在于：几乎不进行不必要的元素交换。交换非常耗时。

对于堆排序，即使所有数据已经有序，您也需要交换100%的元素才能将数组排序。

对于归并排序，情况更糟糕。您需要将100%的元素写入另一个数组，然后将其写回原始数组，即使数据已经有序。

在快速排序中，您不会交换已经有序的元素。如果您的数据完全有序，则几乎不需要交换任何内容！尽管人们对最坏情况十分担心，但选择一个好的枢轴（除了获取数组的第一个或最后一个元素）可以避免最坏情况。如果从第一个、最后一个和中间元素之间的中间元素获取枢轴，则足以避免最坏情况。

快速排序的优势不在于最坏情况，而在于最好情况！在最好情况下，您进行相同数量的比较，但交换的内容很少。在平均情况下，您交换部分元素，但不像堆排序和归并排序那样交换所有元素。这就是为什么快速排序需要的时间最短，交换次数更少，速度更快。

在我的电脑上，以C#实现的以下代码（在发布模式下运行）使用中间枢轴优化比Array.Sort快3秒钟，使用改进的枢轴则快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);
}

- Marquinho Peli

---

+1 对于不同排序算法所需的交换、读写操作次数的考虑。 - Higgs

对于任何确定性、常数时间的枢轴选择策略，你都可以找到一个数组，使其产生 O(n^2) 的最坏情况。仅仅消除最小值是不够的，你需要可靠地选择在特定百分点范围内的枢轴。 - Antimony

我很好奇这是否是您在手写快速排序和C#内置Array.sort之间进行模拟时运行的确切代码？我测试了这段代码，在所有测试中，最好的手写快速排序与Array.sort相同。我在测试中控制了一件事情，即制作两个随机数组的完全相同副本。毕竟，给定的随机化可能比另一个随机化更有利（倾向于最佳情况）。因此，我将相同的集合分别运行。Array.sort每次都赢了（顺便说一下，这是发布版本）。 - Chris

归并排序不必复制100％的元素，除非它是从教科书中非常幼稚的实现。很容易实现它，只需要复制其中50％（两个合并数组的左侧）。也很容易推迟复制，直到您实际上必须“交换”两个元素，因此对于已经排序的数据，您不会有任何内存开销。因此，即使50％实际上是最坏情况，您也可以在0％和50％之间拥有任何东西。 - ddekany

如果有人试图攻击你的服务器，选择一个糟糕的枢轴点的概率是100%。请注意，这里的“枢轴点”指的是快速排序算法中用于划分数据集的元素。 - Antimony

Answer 2

这篇论文有一些分析。

另外，来自维基百科：

快速排序的最直接竞争者是堆排序。堆排序通常比快速排序略慢，但最坏情况下的运行时间始终是 Θ(nlogn)。快速排序通常更快，但仍有可能出现最坏情况，除非采用introsort变体，在检测到糟糕情况时切换到堆排序。如果预先知道需要使用堆排序，则直接使用它将比等待introsort切换更快。

- DVK

---

值得注意的是，在典型的实现中，快速排序和堆排序都不是稳定排序。 - Femi

根据您提供的链接 https://www.cs.auckland.ac.nz/~jmor159/PLDS210/qsort3.html，堆排序在n=100时需要2842次比较，而在n=500时需要53113次比较。这意味着n=500和n=100之间的比率是18倍，并且它与O(N logN)复杂度的堆排序算法不匹配。我猜他们的堆排序实现很可能存在某种错误。 - DU Jiaen

@DUJiaen - 请记住，O（）关注的是在大 N 时的渐近行为，并具有可能的乘数。 - DVK

这与乘数无关。如果一个算法的复杂度为O(N log N)，那么它应该遵循Time(N) = C1 * N * log(N)的趋势。如果你计算Time(500)/Time(100)，显然C1将被消除，结果应该接近于(500 log500) / (100 log100) = 6.7。但从你提供的链接来看，结果是18，这远超出了比例尺。 - DU Jiaen

链接已失效。 - PlsWork

@DUJiaen，n=500 不足以得出统计数据与预测渐近行为不符的结论。 - Nic Szerman

Answer 3

对于大多数情况来说，快速排序与稍微更快的排序并没有什么区别......您只是永远不希望它偶尔变得非常慢。虽然您可以调整快速排序以避免非常慢的情况，但您会失去基本快速排序的优雅。因此，在大多数情况下，我实际上更喜欢堆排序......您可以完全实现其简单优雅性，并且永远不会出现慢速排序。

对于需要在大多数情况下实现最大速度的情况，快速排序可能优于堆排序，但两者都可能不是正确的答案。对于速度至关重要的情况，值得仔细研究情况的细节。例如，在我的一些速度关键代码中，数据已经排序或接近排序（正在索引多个相关字段，这些字段通常同时向上或向下移动，或相反地向上或向下移动，因此一旦您按一个字段排序，则其他字段就被排序或反向排序或接近...任何一种情况都可能导致快速排序失败）。对于这种情况，我都没有实施快排或堆排......相反，我实施了Dijkstra的SmoothSort......它是一种堆排序变体，当数据已排序或接近排序时，它的时间复杂度为O（N）......它不太优雅，也不太容易理解，但很快......如果您想要挑战一些更具挑战性的代码，请阅读 http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF。

- Brian Kennedy

Answer 4

快速排序-堆排序原地混合算法非常有趣，因为它们大多数只需要n * log n次比较就能在最坏情况下达到最优（它们针对渐进符号的第一项是最优的，因此避免了快速排序的最坏情况），额外空间复杂度为O(log n)，并且至少保留了“一半”已排序数据集的良好行为。 Dikert和Weiss在http://arxiv.org/pdf/1209.4214v1.pdf中提出了一种极其有趣的算法：

• 从sqrt(n)个元素的随机样本中选择一个中位数作为枢轴p（通过Tarjan&co的算法，最多可以进行24 sqrt(n)次比较，或通过Schonhage的更加复杂的spider-factory算法进行5 sqrt(n)次比较）；
• 将数组分成两部分，就像快速排序的第一步一样；
• 使较小部分形成堆，并使用O(log n)的额外位来编码堆，其中每个左子节点都具有大于其兄弟的值；
• 递归地提取堆的根，将由根留下的空缺下移，直到达到堆的叶子节点，然后使用来自数组另一部分的适当元素填充空缺；
• 对剩余的非有序数组进行递归（如果p被选择为确切的中位数，则根本不需要递归）。

- Jack D'Aurizio

Answer 5

堆排序具有最坏情况下运行时间为O(n*log(n))的优点，因此在快速排序可能表现不佳的情况下（通常是大部分已排序数据集），堆排序更受欢迎。

- zellio

---

如果选择不良的基准选择方法，例如始终选择第一个或最后一个元素作为基准，则快速排序在大部分已排序数据集上的性能会变差。但是，如果每次选择随机的基准并使用良好的重复元素处理方法，那么出现最坏情况的概率就非常小了。 - Justin Peel

@Justin - 这非常正确，我是在谈论一个天真的实现。 - zellio

@Justin：没错，但是出现严重放缓的可能性总是存在的，即使非常小。对于某些应用程序，即使速度较慢，我也希望确保O（n log n）的行为。 - David Thornley

@JustinPeel 在一个非常大的随机数集合中，如果这些数在一个小范围内（例如8位或16位无符号整数），快速排序算法将总是达到其最坏情况的性能，而不管您选择哪个枢轴。 - GDI512

Answer 6

对我而言，堆排序和快速排序之间有一个非常根本的区别：后者使用递归。在递归算法中，堆随着递归次数增加而增长。如果 n 很小，这无关紧要，但现在我正在对两个矩阵进行排序，n=10^9 !!。程序占用了近10 GB 的内存，任何额外的内存都会使我的计算机开始交换到虚拟磁盘内存。我的硬盘是一个 RAM 硬盘，但仍然交换到它会造成巨大的速度差异。因此，在一个包括可调整维度矩阵、大小未知于程序员的 C++ 统计包中，以及非参数统计类型的排序中，我更喜欢使用堆排序来避免使用非常大的数据矩阵时出现延迟。

- csevcik

---

平均只需要 O(logn) 的内存。递归开销微不足道，假设你的枢轴点不会不幸地选错，否则你就有更大的问题要担心了。 - Antimony

快速排序并不一定是递归的。事实上，将递归算法转化为非递归算法总是可行的。当然，QS的经典演示都涉及到递归，但在实践中并不一定如此。 - gniourf_gniourf

Answer 7

如果你深入到架构层面，我们在缓存内存中使用队列数据结构。所以无论队列中有什么，都会被排序。在快速排序中，我们没有将数组划分为任何长度的问题。但是在堆排序（通过使用数组）中，可能会出现父级不在可用于缓存的子数组中的情况，然后它必须将其带入缓存内存...这需要时间。

这就是为什么快速排序是最好的选择！

- Manav Jain

Answer 8

快速排序和归并排序之间的比较，因为两者都是原地排序的一种类型，所以它们之间存在差异。最坏情况下快速排序的运行时间为O(n^2)，而堆排序的最坏运行时间仍为O(n*log(n))，对于平均数量的数据，快速排序将更加有用。由于它是随机算法，因此在较短的时间内得到正确的答案的概率将取决于您选择的轴元素的位置。

因此：

好的选择： L和G的大小都小于3s/4

不好的选择： L和G中有一个的大小大于3s/4

对于少量数据，我们可以选择插入排序；对于非常大量的数据，我们可以选择堆排序。

- vicky garg

---

尽管归并排序可以使用原地排序实现，但实现起来比较复杂。据我所知，大多数归并排序实现不是原地排序，但它们是稳定的。 - Femi

Answer 9

堆排序建立一个堆，然后重复提取最大项。它的最坏情况是O(n log n)。

但是如果你看到快速排序的最坏情况是O(n2)，你会意识到快速排序对于大数据来说不是一个很好的选择。

所以这使得排序成为一件有趣的事情；我相信之所以有这么多排序算法存在至今，是因为它们在最佳场景下都是“最好”的。例如，如果数据已经排序，冒泡排序可能比快速排序更快。或者如果我们知道要排序的项目的某些信息，那么可能我们可以做得更好。

这可能不能直接回答你的问题，但我想加上我的两分钱。

- KMån

---

永远不要使用冒泡排序。如果您合理地认为数据将被排序，则可以使用插入排序，甚至测试数据以查看它们是否已排序。不要使用冒泡排序。 - vy32

如果你有一个非常大的随机数据集，最好使用快速排序。如果部分有序，则不适用，但如果你开始处理大型数据集，至少应该了解这些。 - Kobor42

Answer 10

在简单的术语中，HeapSort保证了“O(n log n)”的最坏运行时间，而不是QuickSort的“O(n log n)”平均运行时间。通常实际应用中使用QuickSort，因为它通常更快，但当需要对无法适应计算机内存的大型文件进行外部排序时，会使用HeapSort。

- Ahmed Boutaraa