《算法》C++代码 快速排序

       快速排序，简称快排，常称QuickSort、QSort。在排序算法中非常常用，其编程复杂度低，时间复杂度O(logN)，空间复杂度O(N)，执行效率稳定，而且常数很低。

       基本思想就是二分，例如你要将N个数排序，你调用了QSort(1,N)。那么快排会这样做：

1、找出一个数x

2、将N个数分成两部分，左边的都比x小，右边的都比x大

3、分别对两边调用QSort

       很显然，这是二分，递归实现。

　　先说第二步，代码别写得太难看，时间复杂度就是O(N)，扫一遍就可以了。于是，重点便是第一步——我们假设你找x的时间是O(1)，那么如果你的x每次找到的都是中位数，那么算法时间就是O(NlogN)；如果你的x每次找到的都是最边上的数（以至于你将N个数分成了1个和N-1个），那么算法时间就是O(N²)。因此，只有在优秀的选x方法下，快排才能保证O(NlogN)的复杂度。

　　我们来详细讨论一下第一步（下面分析“中位数”的实际含义，以及给出两种常见实现取法，高手可以跳过直接去看代码了~）。

　　我们理想情况是找中位数，但是你不可能真正去找中位数，因为那样的时间是O(N)。新手很头疼，“这咋整？”方法很简单：随便选一个就好了。

　　新手更头疼了……“你随便选一个，选的时间当然是O(1)了，可你凭什么保证算法复杂度不退化？”其实，我也不能保证算法不退化，但我知道从概率上说，我每次都随机选，大部分时候都没退化多少，结果就只有很低很低的概率退化成O(N²)。新手很鄙视，“如果我完全可以给你构造出一组数据，让你每次都选边上的啊！这样不就退化成O(N²)了吗？ ”这点其实是不可能的。因为我不是固定选某个位置的数，而是随机选，所以你根本无法构造，我退化多少，只取决于概率。

　　新手要放弃了……“你这快排复杂度直接取决于概率，可我概统没学好，也不知道快排的退化概率是多少，我怎么敢用啊！万一我用的时候正好退化了咋办！”这点，便是我今天要重点和广大新手说的，你们接触到了一个算法中很重要的概念：随机算法。

　　算法复杂度，只是对算法一个很粗的描述。你知道一个算法的复杂度是O(N²)，其实你只是知道它是两阶而已，根本不知道真正的复杂度。复杂度的常数是多少？是3N²、0.3N²，还是1.3N²？平时我们不分析，是因为我们都按照最大复杂度分析的。题目给你N=1000，你知道算法复杂度O(N²)，又知道常数很大时（例如100）程序不到1s可以运行完，于是你便敢写了。可是现在不行了，算法是随机的，好的时候O(NlogN)常数还很小，坏的时候O(N²)常数还很大，你还敢不分析？

　　可能有人不敢用，觉得只要是概率就不能保证没问题，万一考试碰上就惨了。这种思想一般都是新手才会有，请你务必说服自己！我的理由很简单，概率太高我也不敢用，我的做法是，把概率降到比你某天出门被花盆意外砸死的概率还要低，我就敢用了，因为我确信我不会某天出门被花盆砸死。

　　当然，明确了这一点，现在的问题就是，不会分析怎么办？长远来看，你还是回去好好学学概率，再回来分析得好；短期来看，有没有简单些的方法呢？当然有，就是测试。你随机出很多很多数据，用你写的快排去测，发现他们最惨的也完全可以算作O(NlogN)，那基本就没问题了，因为实际考试和实际应用数据情况也基本是这样。

　　好了，说了这么多，其实只是因为理解快排的思想是很多新手的一道门槛。我希望能通过自己多说些废话，帮助很多新手顺利迈过去。这样，对很多新手以后的算法之路都是有益无害的。下面让我们讨论第一步实际应当如何做：

　　必须明确，如果选择方法过于复杂，那么算法常数会变大；如果方法过于简单，那么算法复杂度会退化。因此综合考虑，加以分析和大量实测，比较常见的既好写又快的写法有两种。假设你有N个数A[1~N]：

1、x=mid(A[1],A[(1+N)/2],A[N])，mid是指取这三个数的中位数。这是最常用的一种方法，如果我没记错的话，这种算法也是C++算法库（algorithm）里面的写法。实际情况表明，这种取法效率很高。

2、x=A[randint(1,N)]，也就是下标取1~N中随机一个数。这也是比较常用的一种方法，好处是真正保证了随机性，但坏处是生成随机数耗时比较高，会导致算法常数变大。

       说了这么多，新手可能会觉得我还是没说明为什么快排的复杂度是O(NlogN)。我只能说，要分析快排复杂度需要很细的分析和大量的数据，有机会我会单独写一篇文章来分析的，现在我只能从概率上告诉你大部分时候都是O(NlogN)，而且快排常数比堆排小不少（时间大概快一倍吧，没实测过，瞎说），能卡快排的数据你也暂时遇不到。我不敢说没有数据能卡快排，但我可以确定，如果不是特意要卡你，这样写快排一定没问题，反正我考试是敢用的。要是真有人死活卡你，那你就写堆排吧，常数大点，但确实不可能被卡。

下面给出我的代码：

 1 inline void swap(int &a,int &b) { int t=a; a=b; b=t; }
 2 
 3 inline int mid(int a,int b,int c)
 4 {
 5     if(a>b) swap(a,b);
 6     if(b>c) swap(b,c);
 7     if(a>b) swap(a,b);
 8     return b;
 9 }
10 
11 void QSort(int A[],int l,int r) // ??????
12 {
13     if(l>=r) return;
14     int i=l,j=r,x=mid(A[l],A[(l+r)>>1],A[r]);
15     while(true)
16     {
17         while(A[i]<x) ++i;
18         while(A[j]>x) --j;
19         if(i>j) break;
20         swap(A[i],A[j]); ++i; --j;
21     }
22     QSort(A,l,j); QSort(A,i,r);
23 }