algorithm - 快速排序与堆排序

Question

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

Answer 1

Heapsort 是 O(N log N) 保证的，这比 Quicksort 中的最坏情况要好得多。 Heapsort 不需要更多内存用于另一个数组来放置 Mergesort 所需的有序数据。那么为什么商业应用程序坚持使用快速排序呢？与其他实现相比，Quicksort 有什么特别之处？

我亲自测试了这些算法，发现 Quicksort 确实有一些特别之处。它运行速度快，比 Heap 和 Merge 算法快得多。

Quicksort 的秘诀在于:它几乎不做不必要的元素交换。交换非常耗时。

使用 Heapsort，即使您的所有数据都已排序，您也将交换 100% 的元素以对数组进行排序。

对于 Mergesort，情况更糟。您将在另一个数组中写入 100% 的元素，然后将其写回原始数组，即使数据已经排序也是如此。

使用快速排序，您不会交换已经排序的内容。如果你的数据是完全有序的，你几乎不会交换任何东西!虽然有很多关于最坏情况的大惊小怪，但在 pivot 的选择上稍作改进，除了获取数组的第一个或最后一个元素之外，都可以避免它。如果从 first、last 和 middle 元素之间的中间元素得到一个 pivot，就足以避免最坏的情况。

Quicksort 的优越之处不是最坏的情况，而是最好的情况!在最好的情况下，你进行相同数量的比较，好吧，但你几乎没有交换任何东西。在一般情况下，您会交换部分元素，而不是所有元素，如 Heapsort 和 Mergesort。这就是给 Quicksort 最好时机的原因。更少的交换，更快的速度。

以下在我的计算机上以 C# 实现，在 Release模式下运行，优于 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);
}