Quicksort vs heapsort

Question

quicksort和heapsort都进行就地排序.哪个更好？什么是首选的应用程序和案例？

Answer 1

Heapsort是O(N log N)保证,比Quicksort的最坏情况要好得多.根据Mergesort的需要,Heapsort不需要更多内存来为另一个数组放置有序数据.那么为什么商业应用程序坚持使用Quicksort？Quicksort有什么特别优于其他实现？

我自己测试了算法,我发现Quicksort确实有一些特别的东西.它运行速度快,比Heap和Merge算法快得多.

Quicksort的秘诀在于:它几乎不会进行不必要的元素交换.交换是耗时的.

使用Heapsort,即使您的所有数据都已经订购,您也要交换100%的元素来订购数组.

使用Mergesort,情况会更糟.您将在另一个数组中编写100%的元素,并将其写回原始数组中,即使已经订购了数据.

使用Quicksort,您不会交换已订购的内容.如果您的数据是完全订购的,那么几乎没有任何交换!虽然关于最坏情况有很多烦恼,但是对于枢轴选择的一点改进,除了获得数组的第一个或最后一个元素之外,可以避免它.如果从第一个,最后一个和中间元素之间的中间元素获得一个枢轴,则避免最坏的情况是足够的.

Quicksort的优势不是最坏的情况,而是最好的情况!在最好的情况下,你做相同数量的比较,好吧,但你几乎没有交换.在一般情况下,您交换部分元素,但不是所有元素,如Heapsort和Mergesort.这就是Quicksort最好的时间.交换更少,速度更快.

我的计算机上的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);
}

Answer 2

http://www.cs.auckland.ac.nz/~jmor159/PLDS210/qsort3.html进行了一些分析.

另外,来自维基百科:

快速排序的最直接竞争对手是heapsort.Heapsort通常比quicksort慢一些,但最坏情况下的运行时间总是Θ(nlogn).Quicksort通常更快,尽管除了在检测到坏情况时切换到heapsort的introsort变体之外,仍然存在最坏情况性能的可能性.如果事先知道heapsort是必要的,直接使用它将比等待introsort切换到它更快.

Answer 3

对于大多数情况来说,快速与快速相关是无关紧要的...你根本不想让它偶尔变得缓慢.虽然您可以调整QuickSort以避免缓慢的情况,但您会失去基本QuickSort的优雅.所以,对于大多数事情,我实际上更喜欢HeapSort ......你可以用它完全简单的优雅来实现它,而且永远不会慢慢排序.

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

Answer 4

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)比较中完成,或者通过更复杂的蜘蛛进行5 sqrt(n)比较 - Schonhage的令人满意的算法);
• 像Quicksort的第一步一样,将数组分为两部分;
• 对最小的部分进行修改并使用O(log n)个额外位来编码堆,其中每个左子的值都大于其兄弟;
• 递归地提取堆的根,向下筛选由根留下的lacune直到它到达堆的叶子,然后用从阵列的其他部分取出的适当元素填充lacune;
• 重复数组的剩余非有序部分(如果选择p作为精确中位数,则根本没有递归).