Quicksort vs heapsort

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

• 选择一个枢轴 p 作为 sqrt (n)元素的随机样本的中值(这可以通过 Tarjan & co 算法在最多24 sqrt (n)的比较中进行，或者通过 Schonhage 更复杂的蜘蛛工厂算法进行5 sqrt (n)比较) ;
• 像 Quicksort 的第一步那样将数组分成两部分;
• 将最小的部分堆积起来，并使用 O (log n)额外位来编码堆，其中每个左子节点的值都大于其同级节点的值;
• 递归地提取堆的根，筛选堆根留下的间隙，直到它到达堆的一片叶子，然后用从数组的其他部分提取的适当元素填充间隙;
• 遍历数组中剩余的无序部分(如果选择 p 作为精确的中位数，则根本不存在递归)。

Heapsort 是 O (N log N)担保的，这比 Quicksort 的最坏情况要好得多。Heapsort 不需要更多的内存来存放 Mergesort 所需要的有序数据。那么，为什么商业应用程序还坚持使用 Quicksort 呢？什么样的快速排序比其他的实现更特别？

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

The secret of Quicksort is: It almost doesn't do unnecessary element swaps. Swap is time consuming.

使用 Heapsort，即使您的所有数据都已经排序，您也需要交换100% 的元素来排序数组。

With Mergesort, it's even worse. You are going to write 100% of elements in another array and write it back in the original one, even if data is already ordered.

使用快速排序，您不需要交换已经订购的内容。如果您的数据是完全有序的，那么您几乎不需要交换任何东西！虽然在最坏情况下会有很多麻烦，但对枢轴的选择做一点改进，除了获得数组的第一个或最后一个元素之外，其他任何方法都可以避免这种情况。如果您从第一个、最后一个和中间元素之间的中间元素获得一个枢轴，那么就足以避免最坏的情况。

在 Quicksort 优越的不是最坏的情况，而是最好的情况！在最好的情况下，你做同样数量的比较，好吧，但你几乎没有交换任何东西。在一般情况下，你交换部分元素，但不是全部元素，就像在 Heapsort 和 Mergesort。这给了快排最好的时间。更少的交换，更快的速度。

在我的计算机上，以发布模式运行的 C # 实现击败了 Array。排序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);
}

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

在实际应用中，堆排序比快速排序慢的原因是快速排序的访问局部性(“ https://en.wikipedia.org/wiki/Locality_of_reference”)更好，因为数据元素位于相对较近的存储位置。具有强大访问局部性的系统是性能优化的最佳候选者。然而，堆排序可以处理更大的跳跃。这使得快速排序对于较小的输入更有利。

回答最初的问题，并在这里提出其他一些意见:

I just compared implementations of selection, quick, merge, and heap sort to see how they'd stack up against each other. The answer is that they all have their downsides.

译者: Quick is the best general purpose sort (reasonably fast, stable, and mostly in-place) 就个人而言，我更喜欢堆排序，除非我需要一个稳定的排序。

选择 -N ^ 2-它实际上只适用于少于20个元素左右的情况，那么它的性能就会超过。除非您的数据已经排序，或者非常非常接近排序。N ^ 2变得非常慢，非常快。

根据我的经验，快速并不总是 那个快速。使用快速排序作为一般排序的好处是它相当快，而且稳定。它也是一个原地算法，但是由于它通常是递归实现的，它将占用额外的堆栈空间。它也落在 O (n logn)和 O (n ^ 2)之间。某些类型的时机似乎证实了这一点，特别是当值落在一个很窄的范围内。它比对10,000,000条目进行选择排序快得多，但比合并或堆慢得多。

合并排序保证为 O (n logn) ，因为它的排序不依赖于数据。它只是做它该做的，不管你给它什么值。它也是稳定的，但是如果您不注意实现的话，非常大的排序可能会使您的堆栈崩溃。有一些复杂的就地合并排序实现，但通常需要在每个级别中添加另一个数组，以便将值合并到。如果这些数组位于堆栈上，则可能会遇到问题。

堆排序是 max O (n log n) ，但在许多情况下更快，具体取决于在 log n 深度堆中向上移动值的距离。堆可以很容易地在原始数组中就地实现，因此它不需要额外的内存，而且它是迭代的，所以在递归时不用担心堆栈溢出。对于堆排序，巨大的缺点是它不是一个稳定的排序，这意味着如果您需要它，那么它就是正确的。

对我来说，heapsort 和 Quick sort 有一个非常根本的区别: 后者使用递归。在递归算法中，堆随着递归次数的增加而增长。如果 N很小，这并不重要，但是现在我正在排序 N = 10 ^ 9的两个矩阵! ！.该程序需要近10GB 的内存和任何额外的内存将使我的计算机开始交换到虚拟磁盘内存。我的磁盘是一个 RAM 磁盘，但仍然交换到它使一个 huge difference in speed。因此，在用 C + + 编码的 statpack 中，包含可调维度矩阵，程序员事先不知道其大小，以及非参数统计类型的排序，我更喜欢堆排序，以避免在使用非常大的数据矩阵时出现延迟。

如果你进入体系结构层次... ... 我们在缓存内存中使用队列数据结构，所以任何在队列中可用的数据都会被排序。在快速排序中，我们可以将数组划分为任何长度... ... 但在堆排序中(通过使用数组) ，可能会发生父数组不存在于缓存中可用的子数组中，然后它不得不将其放入缓存内存中... ... 这是很耗时的。 这是快速排序是最好的! ！

用简单的术语 > 堆排序保证了“ O (n log n)”在最坏情况下的运行时间，而不是快速排序的运行时间 “ O (n logn)”的平均 ~ 运行时间。快速排序通常用于实践中，因为它通常更快，但 当您需要对不适合您的内存的大文件进行排序时，HeapSort 用于外部排序 电脑。