108

快速排序和堆排序都进行就地排序。哪个更好？哪些应用和案例是首选？

4

12 回答 12

155

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-15T03:55:48.080 回答
68

这篇论文有一些分析。

此外，来自维基百科：

快速排序最直接的竞争对手是堆排序。堆排序通常比快速排序慢一些，但最坏情况下的运行时间总是 Θ(nlogn)。快速排序通常更快，尽管除了 introsort 变体外，仍有可能出现最差情况的性能，当检测到坏情况时，它会切换到堆排序。如果事先知道 heapsort 是必要的，那么直接使用它会比等待 introsort 切换到它更快。

于 2010-03-18T05:48:13.747 回答
16

在大多数情况下，快一点与快一点是无关紧要的……你根本不希望它偶尔变得慢。尽管您可以调整 QuickSort 以避免出现缓慢的情况，但您会失去基本 QuickSort 的优雅。所以，对于大多数事情，我实际上更喜欢 HeapSort ......您可以以其完全简单的优雅来实现它，并且永远不会得到慢排序。

对于大多数情况下您确实需要最大速度的情况，QuickSort 可能比 HeapSort 更受欢迎，但两者都不是正确的答案。对于速度关键的情况，值得仔细检查情况的细节。例如，在我的一些速度关键代码中，数据已经排序或接近排序是很常见的（它正在索引多个相关字段，这些字段通常要么一起上下移动，要么彼此相对地上下移动，因此，一旦您按一个排序，其他排序或反向排序或关闭......其中任何一个都可以杀死 QuickSort）。对于那种情况，我没有实现……相反，我实现了 Dijkstra 的 SmoothSort……一个 HeapSort 变体，当已经排序或接近排序时为 O(N)……它不是那么优雅，也不太容易理解，但很快……阅读http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF如果您想要一些更具挑战性的代码。

于 2011-10-03T05:10:30.127 回答
6

Quicksort-Heapsort 就地混合也非常有趣，因为它们中的大多数只需要在最坏情况下进行 n*log n 比较（它们相对于渐近的第一项是最优的，因此它们避免了最坏的情况的快速排序），O（log n）额外空间，并且它们至少保留了快速排序对于已排序数据集的良好行为的“一半”。Dikert 和 Weiss 在http://arxiv.org/pdf/1209.4214v1.pdf中提出了一个非常有趣的算法：

  • 选择一个枢轴 p 作为 sqrt(n) 元素的随机样本的中位数（这可以通过 Tarjan&co 的算法在最多 24 个 sqrt(n) 比较中完成，或者通过更复杂的蜘蛛进行 5 个 sqrt(n) 比较-Schonhage的工厂算法）；
  • 与快速排序的第一步一样，将您的数组分成两部分；
  • 堆化最小的部分并使用 O(log n) 额外的位来编码一个堆，其中每个左孩子的值都大于其兄弟；
  • 递归提取堆的根，筛选根留下的空白，直到它到达堆的叶子，然后用从数组的另一部分取出的适当元素填充空白；
  • 递归数组的剩余无序部分（如果选择 p 作为确切的中位数，则根本没有递归）。
于 2013-01-21T15:23:51.230 回答
2

堆排序的好处是具有O(n*log(n))的最坏运行情况，因此在快速排序可能表现不佳的情况下（通常主要是排序的数据集）堆排序是更可取的。

于 2010-03-18T05:48:54.850 回答
2

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

所以一个

好调用： L和G的大小均小于3s/4

Bad call： L 和 G 之一的大小大于 3s/4

对于少量数据，我们可以进行插入排序，对于大量数据，我们可以进行堆排序。

于 2012-09-26T17:18:17.570 回答
2

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

于 2016-04-16T00:08:06.330 回答
2

好吧，如果您进入架构级别...我们在缓存中使用队列数据结构。因此，队列中可用的内容将被排序。在快速排序中，我们将数组划分为任何长度都没有问题...但是在堆中排序（通过使用数组）可能会发生父级可能不存在于缓存中可用的子数组中，然后它必须将其带入缓存......这很耗时。那是最好的快速排序！

于 2016-05-20T21:03:21.560 回答
1

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

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

所以这使得排序成为一件有趣的事情；我相信今天有这么多排序算法存在的原因是因为它们在最好的地方都是“最好的”。例如，如果数据已排序，冒泡排序可以执行快速排序。或者，如果我们对要排序的项目有所了解，那么我们可能会做得更好。

这可能无法直接回答您的问题，我想我会加两分钱。

于 2010-03-18T07:43:29.993 回答
1

在处理非常大的输入时，堆排序是一个安全的选择。渐近分析表明，Heapsort 在最坏情况下的增长顺序是Big-O(n logn)，这比 Quicksort 的Big-O(n^2)最坏情况要好。然而，在大多数机器上，堆排序实际上比实现良好的快速排序要慢一些。Heapsort 也不是一个稳定的排序算法。

堆排序在实践中比快速排序慢的原因是由于快速排序中更好的参考局部性（“ https://en.wikipedia.org/wiki/Locality_of_reference ”），其中数据元素位于相对较近的存储位置。表现出很强的参考局部性的系统是性能优化的绝佳候选者。然而，堆排序处理更大的飞跃。这使得快速排序更适合较小的输入。

于 2015-11-26T17:02:38.450 回答
1

简单来说 >> HeapSort 保证了“O(n log n)”的~worst-case~运行时间，而不是 QuickSort 的~平均~“O(n log n)”运行时间。QuickSort 通常在实践中使用，因为它通常更快，但是当您需要对不适合计算机内存的大文件进行排序时，HeapSort 用于外部排序。

于 2020-09-19T11:07:54.650 回答
-1

要回答原始问题并在此处解决其他一些评论：

我只是比较了选择、快速、合并和堆排序的实现，看看它们是如何相互叠加的。答案是它们都有自己的缺点。

TL;DR：快速是最好的通用排序（相当快速、稳定且主要是就地排序）我个人更喜欢堆排序，除非我需要稳定的排序。

选择 - N^2 - 它真的只适用于少于 20 个左右的元素，然后它就表现出色了。除非您的数据已经排序，或者非常非常接近排序。N^2 变得非常慢非常快。

快速，根据我的经验，实际上并不是一直都那么快。使用快速排序作为一般排序的好处是它相当快且稳定。它也是一种就地算法，但由于它通常是递归实现的，因此会占用额外的堆栈空间。它也介于 O(n log n) 和 O(n^2) 之间。某些时间似乎证实了这一点，尤其是当值落在一个狭窄的范围内时。它比对 10,000,000 个项目的选择排序快得多，但比合并或堆慢。

合并排序保证 O(n log n)，因为它的排序不依赖于数据。它只是做它所做的，不管你给它什么值。它也很稳定，但是如果您不小心实现，那么非常大的排序可能会炸毁您的堆栈。有一些复杂的就地合并排序实现，但通常您需要在每个级别中使用另一个数组来合并您的值。如果这些数组存在于堆栈中，您可能会遇到问题。

堆排序最大 O(n log n)，但在许多情况下更快，这取决于您必须将值向上移动到 log n 深堆多远。堆可以很容易地在原始数组中就地实现，所以它不需要额外的内存，而且它是迭代的，所以递归时不用担心堆栈溢出。堆排序的巨大缺点是它不是一个稳定的排序，这意味着如果你需要它就可以了。

于 2016-04-09T21:32:37.643 回答