选主元
1、选择最左边的第一个元素为主元（普通版快速排序）
假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数。为了方便，就让第一个数6作为基准数吧。接下来，需要将这个序列中所有比基准数大的数放在6的右边，比基准数小的数放在6的左边，类似下面这种排列：
3 1 2 5 4 6 9 7 10 8
在初始状态下，数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置，假设这个位置是k。现在就需要寻找这个k，并且以第k位为分界点，左边的数都小于等于6，右边的数都大于等于6。想一想，你有办法可以做到这点吗？
排序算法显神威
方法其实很简单：分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边（即i=1），指向数字6。让哨兵j指向序列的最右边（即=10），指向数字。
首先哨兵j开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵j先出动，这一点非常重要（因为基准数在左边,从右边开始找,则i和j一定会相会在一个小于等于基准数的值,交换之后能保证,小的在基准数左边,大的在基准数右边。）。哨兵j一步一步地向左挪动（即j--），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。
现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下：
6 1 2 5 9 3 4 7 10 8
到此，第一次交换结束。接下来开始哨兵j继续向左挪动（再友情提醒，每次必须是哨兵j先出发）。他发现了4（比基准数6要小，满足要求）之后停了下来。哨兵i也继续向右挪动的，他发现了9（比基准数6要大，满足要求）之后停了下来。此时再次进行交换，交换之后的序列如下：
6 1 2 5 4 3 9 7 10 8
第二次交换结束，“探测”继续。哨兵j继续向左挪动，他发现了3（比基准数6要小，满足要求）之后又停了下来。哨兵i继续向右移动，糟啦！此时哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下：
3 1 2 5 4 6 9 7 10 8
到此第一轮“探测”真正结束。此时以基准数6为分界点，6左边的数都小于等于6，6右边的数都大于等于6。回顾一下刚才的过程，其实哨兵j的使命就是要找小于基准数的数，而哨兵i的使命就是要找大于基准数的数，直到i和j碰头为止。
OK，解释完毕。现在基准数6已经归位，它正好处在序列的第6位。此时我们已经将原来的序列，以6为分界点拆分成了两个序列，左边的序列是“3 1 2 5 4”，右边的序列是“9 7 10 8”。接下来还需要分别处理这两个序列。因为6左边和右边的序列目前都还是很混乱的。不过不要紧，我们已经掌握了方法，接下来只要模拟刚才的方法分别处理6左边和右边的序列即可。现在先来处理6左边的序列现吧。
左边的序列是“3 1 2 5 4”。请将这个序列以3为基准数进行调整，使得3左边的数都小于等于3，3右边的数都大于等于3。好了开始动笔吧
如果你模拟的没有错，调整完毕之后的序列的顺序应该是：
2 1 3 5 4
OK，现在3已经归位。接下来需要处理3左边的序列“2 1”和右边的序列“5 4”。对序列“2 1”以2为基准数进行调整，处理完毕之后的序列为“1 2”，到此2已经归位。序列“1”只有一个数，也不需要进行任何处理。至此我们对序列“2 1”已全部处理完毕，得到序列是“1 2”。序列“5 4”的处理也仿照此方法，最后得到的序列如下：
1 2 3 4 5 6 9 7 10 8
对于序列“9 7 10 8”也模拟刚才的过程，直到不可拆分出新的子序列为止。最终将会得到这样的序列，如下
1 2 3 4 5 6 7 8 9 10
到此，排序完全结束。细心的同学可能已经发现，快速排序的每一轮处理其实就是将这一轮的基准数归位，直到所有的数都归位为止，排序就结束了。下面上个霸气的图来描述下整个算法的处理过程。
这是为什么呢？
快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。其实快速排序是基于一种叫做“二分”的思想。1 typedef int ElementType; 2 3 void Swap(ElementType *a, ElementType *b) 4 { 5 ElementType tmp = *a; 6 *a = *b; 7 *b = tmp; 8 } 9 10 11 void QSort(ElementType A[], int Left, int Right)12 {13 if(Left < Right) 14 { 15 int pivot = A[Left];16 int i, j;17 i = Left;18 j = Right;19 20 while(i != j)21 {22 //顺序很重要，要先从右边开始找23 while(A[j] >= pivot && i < j) //i一定要小于j，以避免j刹不住车而越过i24 j--;25 //再找右边的26 while(A[i] <= pivot && i < j) //i一定要小于j，以避免i刹不住车而越过j27 i++;28 //如果i比j小，则交换两个数在数组中的位置29 if(i < j)30 Swap(&A[i], &A[j]);31 }32 //i与j相等时，将基准数归位33 Swap(&A[Left], &A[i]);34 35 QSort(A,Left,i-1);//继续处理左边的，这里是一个递归的过程36 QSort(A,i+1,Right);//继续处理右边的 ，这里是一个递归的过程}37 }38 }39 40 41 //快速排序统一接口42 void QuickSort(ElementType A[], int N)43 {44 QSort(A, 0, N-1);45 } 注意：
(1) 递归的退出条件？
递归的退出条件为 Left >= Right, 比如，对3,1使用快速排序：
进入递归之前的顺序为1,3，此时主元为3，进入递归后：
左侧递归 ： QSort(A,Left,i-1); // 3的左边只有元素1，所以此时这个递归函数内部Left == Right，递归可以直接退出
右侧递归 : QSort(A,i+1,Right) //3的右边无元素，所以此时这个递归函数内部Left > Right，递归可以直接退出
(2) 基准已经选在最左边， 为什么首先要从右边往左边开始找？
之所以要从右边开始找,因为基准数在左边,从右边开始找,则i和j一定会相会在一个小于等于基准数的值,交换之后能保证,小的在基准数左边,大的在基准数右边。
如果每次都选取第一个元素为主元，则最坏情形为O(n^2)。
所以建议主元选取方法为：选头中尾元素的中位数。(三数中值分割法)
2、选择头中尾元素的中位数作为主元（三数中值分割法）
1 #define Cutoff 100 2 3 void Swap(ElementType *a, ElementType *b) 4 { 5 ElementType tmp = *a; 6 *a = *b; 7 *b = tmp; 8 } 9 10 //选主元11 ElementType Median3( ElementType A[], int Left, int Right )12 {13 int Center = (Left + Right) / 2;14 15 if(A[ Left ] > A[ Center ])16 Swap( &A[ Left ], &A[ Center ] );17 if(A[ Left ] > A[ Right ])18 Swap( &A[ Left ], &A[ Right ] );19 if(A[ Center ] > A[Right])20 Swap(&A[ Center ], &A[ Right ]);21 22 /*此时A[Left] <= A[Center] <= A[Right] ,所以三者中位数(即主元)为A[Center]*/23 Swap(&A[ Center ], &A[ Right-1 ]); // 将主元藏在最右边, 即A[Right]的左侧24 25 /*A[Left]此时肯定小于A[Center], A[Right]肯定大于A[Center], 26 并且两者已经分居在主元的两侧,又把主元藏在了A[Right-1], 27 所以只需考虑A[Left+1]与A[Right-2]之间的元素*/28 return A[ Right-1 ]; //返回主元29 }30 31 //快速排序的递归函数32 void QSort( ElementType A[], int Left, int Right )33 {34 int Pivot, i, j;35 if( Right-Left >= 3 ) //如果序列元素充分多，进入快排36 {37 Pivot = Median3( A, Left, Right ); //选主元38 /*a*/ i = Left;39 j = Right - 1;40 while(1) //将序列中比主元小的移动到主元左边，大的移动到右边41 {42 /*b*/ while( A[++i] < Pivot ) {} 43 while( A[--j] > Pivot ) {} 44 if( i < j ) 45 Swap( &A[i], &A[j] );46 else47 break;48 }49 Swap( &A[i], &A[Right-1] ); //此时i左边的元素都比主元小，右边的都比主元大，所以i为主元的正确位置50 QSort( A, Left, i-1 ); //递归解决左边51 QSort( A, i+1, Right ); //递归解决右边52 }53 else54 InsertionSort( A+Left, Right-Left+1 ); //元素个数小于等于2时，必须用简单排序处理55 }56 57 58 //快速排序的统一接口59 void QuickSort( ElementType A[], int N )60 {61 QSort( A, 0, N-1 );62 }
注意：
( 1 ) 不能把a, b处的程序改为
i = Left + 1; j = Right - 2;while( A[i] < Pivot ) ++i;while( A[j] > Pivot ) --j;
否则将出错，因为当A[ i ] = A[ j ] = pivot 的时候，会产生一个无限循环 ( 死循环 ).
( 2 ) 当A[ i ] 或 A[ j ]与pivot时，i和j必须停下来做交换，否则如果数组中全部元素都相等的话，i 将一直移动到倒数第二个位置，
这样将会使一趟过后主元只向左移动一个位置，使得运行时间变为O(n^2).
( 3 ) Cutoff的值至少要为3，否则对两个数或一个数无法进行三数中值的选择，且只有一个数的时候，Left与Right相等。数组会越界。
当间隔( Right - Left )小于2时，必须进行简单排序，不然快速排序会出现错误。
因为：
(1)当 Right - Left 等于 0时,快排的元素个数只有一个，当这个数位于数组的最后位置时，当++i后，再访问A[ i ], 就会出现数组越界的错误！
(2) 当 Right - Left 等于 1时，快排的元素个数只有2个，假设这两个数是4,5且为数组最后两个数，那么选出的主元就是4，当 --j 后，A[ j ]就会访问到4前面的那个数，
但你只是对4,5进行快排，当j访问到前面的数时， 就导致快排出现错误的结果。且如果这两个数是数组前两个数的话，--j 就会导致数组越界。
(3)快速排序只能将小于主元的数放在主元左边，大于主元的数放在右边，某次快排后把5,4排在了主元3的右边，但并不能继续把5和4排好序。所以此时必须借助简单排序。比如，
若缺少下面这条简单排序的语句， 比如对A[8] = { 8, 1, 4, 9, 0, 3, 5, 2}，快速排序将会出现错误，输出为0,1,2,3,5,4,8,9。
else InsertionSort( A+Left, Right-Left+1 );
3、快速排序存在的问题
