快速排序

数据

• 平均时间复杂度：O(nlogn)

• 最好时间复杂度：O(nlogn)

• 最坏时间复杂度：O(n^2)

• 空间复杂度：O(logn)

• 排序方式：In-Place

• 稳定性：不稳定

描述

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：

快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

动图

C#实现

public class QuickSort
{
    public static void Sort<T>(IList<T> list, Func<T, T, bool> compare)
    {
        if (list == null || list.Count < 2)
        {
            return;
        }

        InternalSort(list, 0, list.Count - 1, compare);
    }

    public static void InternalSort<T>(IList<T> list, int low, int high, Func<T, T, bool> compare)
    {
        if (high <= low)
        {
            return;
        }

        int j = Partition(list, low, high, compare);
        InternalSort(list, low, j - 1, compare);
        InternalSort(list, j + 1, high, compare);
    }

    public static int Partition<T>(IList<T> list, int low, int high, Func<T, T, bool> compare)
    {
        var i = low;
        var j = high + 1;
        var pivot = list[low];

        while (true)
        {
            while (compare(list[++i], pivot))
            {
                if (i == high)
                {
                    break;
                }
            }

            while (compare(pivot, list[--j]))
            {
                if (j == low)
                {
                    break;
                }
            }

            if (i >= j)
            {
                break;
            }

            SortHelper.Exchange(list, i, j);
        }
        SortHelper.Exchange(list, low, j);

        return j;
    }
}

Lua实现