logo标签列表

快速排序相对于堆排序的优越性

algorithmsortingbig-oquicksortheapsort
53

堆排序的最坏时间复杂度是O(nlogn)，而快速排序的时间复杂度为O(n^2)。 但实际证据表明，快速排序更优秀。为什么呢？

1
最坏情况发生在元素已经排序的情况下 - 这是相对罕见的情况 - 如果您的系统可能出现这种情况，可以通过首先进行简单的洗牌来轻松避免。参考局部性是QR快速运行时性能的关键。 - Paul
1
@Paul 简单的洗牌并不能解决快速排序中数组中重复值的问题。 - Manohar Reddy Poreddy
6个回答
66

主要因素之一是快速排序具有更好的本地性——下一个要访问的元素通常在刚刚查看过的元素附近，相比之下，堆排序跳动较多。由于接近的元素可能会被缓存在一起，因此快速排序往往更快。

然而，快速排序的最坏情况性能明显差于堆排序。由于某些关键应用程序需要保证速度性能，对于这些情况，堆排序是正确的选择。

对于小的工作集，参考局部性是避免不必要页面错误的关键问题。在函数末尾调用左侧分区排序，然后进行尾递归优化右侧分区是一个有力的论据。 - EvilTeach
1
但实际操作中还不够强。始终首先对最小的分区进行排序，以避免堆栈溢出。 - Stephan Eggermont
@StephanEggermont：如果左分区包含数百万个项目，而右分区只有两个项目，显然应该先对右分区进行排序。但是，如果左分区首先进行排序，除非左分区比右分区大三倍以上，否则会有任何问题吗？最坏情况下堆栈深度将增加，但仅增加一个常数因子。 - supercat
@supercat，那只会更慢。左侧或右侧先进行分区对参考位置的局部性没有实际影响。 - Stephan Eggermont
23
堆排序的时间复杂度为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);
}
8
1

大O符号表示排序n个项目所需的时间受到函数c*n*log(n)的上限约束，其中c是一些未指定的常数因子。对于快速排序和堆排序，常量c没有理由相同。因此，真正的问题是：为什么您期望它们同样快呢？

实践中，快速排序总是比堆排序要快一些，但最近差别变得更大了，因为如前所述，内存访问的局部性对执行速度非常重要。

0

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

0
如已提到，与堆排序相比，快速排序具有更好的引用局部性，但最坏情况下的复杂度为O(n^2)。
std::sort 使用内省排序实现：它大部分时间运行快速排序，但如果检测到由于糟糕的枢轴选择导致运行时不佳，它将切换到堆排序。在这种情况下，您将获得一种保证的O(nlog(n))复杂度和快速排序的速度，几乎每次都选择快速排序。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接