算法手记（7）快速排序

终于到了经典的快排了，作为20世纪科学和工程领域十大算法之一，自60年代发明以来，一直吸引着一批批工程师和科学家对其改进，今天我们就分析快排算法以及它的几种改进方案。

快速排序

概述：
快速排序算法也是基于分治思想的方案，与归并排序不同的是，它是原地排序，同时可以将长度为N的数组排序所需的时间和NlogN成正比，我们已经学习过的算法都无法将这两个优点结合起来。

快速排序流行的原因是因为它实现简单，适用于各种不同的输入数据且在一般应用中比其他算法要快得多，他可能是使用最广泛的算法了。

分析：

快排是一种分治的排序算法。它讲一个数组分成两个子数组，将两部分独立地排序，当两个子数组都有序时整个数组自然就有序啦。在快速排序中，切分(Partition)的位置取决于数组的内容，该算法的关键也在于切分，这个过程需要满足3个条件：

1.对于某个j，a[j]已经排定；

2.a[lo]到a[j-1]中的所有元素都不大于a[j];

3.a[j+1]到a[hi]中的所有元素都不小于a[j];

根据归纳法不难证明他能正确的排序数组：如果左子数组和右子数组都是有序的，那么左子数组，切分元素，右子数组组成的结果数组也一定是有序的。它是一个随机化算法，因为它在排序之前顺序会被打乱，这么做是希望可以预测该算法的性能特征。

这里切分的一般策略是先随意地取a[lo]为切分元素，然后我们分别自左向右扫描直到找到一个大于等于它的元素，再自右向左扫描直到找到一个小于等于它的元素，我们交换这两个元素的位置。如此继续，就可以保证坐指针i的元素不大于切分元素，右指针j的元素不小于切分元素，最后当i和j相遇时，将a[lo]与a[j]交换，然后返回j即可。

实现：

public class Quick
    {
        public static void sort(IComparable[] a)
        {

              RandomShuffle.shuffle(a);

            sort(a, 0, a.Length - 1);
        }
        private static void sort(IComparable[] a, int lo, int hi)
        {
            if (hi <= lo) return;
            int j = partition(a, lo, hi);
            sort(a, lo, j - 1);
            sort(a, j + 1, hi);
        }

        private static int partition(IComparable[] a, int lo, int hi)
        {
            int i = lo, j = hi + 1;
            IComparable v = a[lo];
            while (true)
            {
                while (less(a[++i], v)) if (i == hi) break;
                while (less(v, a[--j])) if (i == lo) break;
                if (i >= j) break;
                exch(a, i, j);
            }
            exch(a, lo, j);
            return j;
        }
        private static bool less(IComparable i, IComparable j)
        {
            return i.CompareTo(j) < 0;
        }
        private static void exch(IComparable[] a,int i, int j)
        {
            var temp=a[i];
            a[i] = a[j];
            a[j] = temp;
        }
        public static void test(int size)
        {
            var stopWatch = new Stopwatch(DateTime.Now);
            Data[] data = new Data[size];
            Random rd = new Random();
            for (int i = 0; i < size; i++)
            {
                data[i] = new Data { value = rd.Next(10000000) };
                Console.WriteLine(data[i]);
            }
            Console.WriteLine("After sort:");

            Quick.sort(data);
            for (int i = 0; i < size; i++)
            {
                Console.WriteLine(data[i]);
            }
            stopWatch.elapsedTime();
           
        }
        public static void Main(string[] args)
        {
            test(100);
        }
    }

注意点：

1.原地切分

如果使用辅助数组，则可以很轻松的实现切分，但是将切分后的数组复制回去的开销可能是我们无法承受的，这会大大降低算法的排序速度。

2.别越界

如果切分元素是数组中最小或最大的元素，我们就需要确保扫描数组别跑出边界，需要实现明确地检测来防止这种情况。

3.保持随机性

数组元素顺序是被打乱过的，它的所有子数组也都是随机排序的，这对预测算法的运行时间很重要，同时也能减小最坏情况发生几率。

4.终止循环

有经验的程序员都明白终止循环需要格外小心，快速排序的切分循环也不例外。一个常见的错误是没有考虑到数组中可能包含和切分元素的值相同的其他元素。

5.处理切分值有重复的情况

这里的实现算法里，左侧扫描最好在遇到大于等于切分值时停下，右侧扫描在遇到小于等于切分值停下。尽管这样可能将一些等值的元素交换，但在某些典型应用中，这可以避免算法的运行时间变为平方级别。

6.终止递归

有经验的程序员在保证递归总是能够结束也是需要小心的。快速排序的一个常见错误就是不能保证将切分元素放入正确的位置，从而导致程序在切分元素正好是最大或最小值时陷入了无限的递归之中。

总结：

数学上对快速排序已经有了详尽的分析，因此我们能够精确说明它的性能。快速排序切分方法的内循环会用一个递增的索引将数组元素和一个定值比较，很难想象排序算法中还有比这个更短小的内循环了。

快速排序的另一个优势在于它的比较次数较少，快速排序最好的情况是每次都能正好将数组对半分，这种情况下正好满足分治递归的Cn=2Cn/2+N公式，即Cn~NlogN。

尽管快速排序有很多优点，但它的基本实现有一个潜在的缺点：在切分不平衡时会极为低效。我们在快排之前将数组随机打乱就是为了防止此种情况，这样可以将糟糕的切分情况可能性降到最低。