1）基本思想

快速排序的基本思想是在数组中选择一个枢纽元素，然后分别从数组的开始和结束位置处开始遍历数组，将比枢纽元素小的都移到枢纽元素的左边，将比枢纽元素大的元素都移到它的右边，然后递归对枢纽元素前面的元素和后面的元素进行排序。即：

这里的一个关键地方是如何选取枢纽元，有三种选择：

a. 选取数组的第一个元素 这种策略就是比较懒惰的将得到的数组的第一个元素作为枢纽元，如果数组元素是随机排列的，这是可行的。但如果数组是预排序或反序的，那么这将造成数组几乎所有的元素都落在S1或者S2中，这样一来，最终的时间复杂度将达到O(N^2)。

b. 利用随机数生成器产生随机枢纽元 一般来讲除非运气比较差会导致随机产生的枢纽元导致a中的结果，否则还是比较安全的。但是随机数生成器的使用成本还是很高的，它会抵消节省下来的平均运行时间。

c.  三数中值法 这种方式分别取出数组元素的第一个元素，中间的元素和最后一个元素进行排序并将中值作为枢纽元，最终的结果是三者中最小的元素放在了数组的起始位置，最大的元素放到了数组的最后的位置，三者中的中值放在了中间位置上。

这里选择c中的方法来选取枢纽元，并将枢纽元移至数组的倒数第二个位置，从数组的第二个位置和数组的倒数第三个位置开始遍历数组，设为位置i和j，当i处的元素大于等于枢纽元时停止，当j位置的元素小于等于枢纽元时停止，如果i < j, 交换两位置处的元素，然后i和j继续相向遍历，直到两个位置指向同一位置或交错时，此时，交换i处的元素和枢纽元。这样的结果就是枢纽元前面的元素都比它小或者等于它，枢纽元后面的元素都比它大或者相等。

采用c中方案的一个好处就是i和j不会有越界风险，因为数组的第一个元素比枢纽元小，所以j不会越界，又因为倒数第二个位置是枢纽元，i停在大于等于枢纽元的位置，所以i也不会越界。

需要注意的地方是，在遍历到等于枢纽元的位置时，不管i或者j这里都采用停止而非继续向前的策略，这里简单的做一个反例：对于一个全部相同的数组来说，如果i和j在A[i] = A[j]时不交换继续向前，那么必须有一个方法防止i或者j越界，并且最终枢纽元还是被交换到i最后到过的位置，即倒数第二个位置，最终导致两个极不均衡的数组，时间复杂度为O(n^2)。而如果在相等处采取交换的策略，那么最终得到的是几乎均等的数组，排序的复杂度为O(NlogN)，i和j会交错，所以不用担心越界风险。

2）算法实现 

1 #include "stdafx.h"  2 #include 
      
         3 using namespace std;  4   5 const int cutOff = 3;  6   7 void swap(int* a, int* b)  8 {  9     int temp = *a; 10     *a = *b; 11     *b = temp; 12 } 13  14 int Media3(int A[], int left, int right) 15 { 16     int center = (left + right)/2; 17     if(A[left] > A[center]) 18     { 19         swap(&A[left], &A[center]); 20     } 21     if(A[left] > A[right]) 22     { 23         swap(&A[left], &A[right]); 24     } 25     if(A[center] > A[right]) 26     { 27         swap(&A[center], &A[right]); 28     } 29     swap(&A[center], &A[right-1]); 30  31     return A[right-1]; 32 } 33  34 void insertSort(int A[], int left, int right) 35 { 36     for(int i = left + 1; i <= right; i ++) 37     { 38         int temp = A[i]; 39         int j = i; 40         for(; j > 0; j --) 41         { 42             if(A[j-1] > temp) 43             { 44                 A[j] = A[j-1]; 45             } 46             else 47                 break; 48         } 49         A[j] = temp; 50     } 51 } 52  53 void qSort(int A[], int left, int right) 54 { 55     int pivot = Media3(A, left, right); 56     int i = left; 57     int j = right - 1; 58     if(left + cutOff <= right) 59     { 60         for(;;) 61         { 62             while(A[++i] < pivot) { } 63             while(A[--j] > pivot) { } 64             if(i < j) 65             { 66                 swap(&A[i], &A[j]); 67             } 68             else 69             { 70                 break; 71             } 72         } 73         swap(&A[i], &A[right-1]); 74         qSort(A, left, i - 1); 75         qSort(A, i + 1, right); 76     } 77     else 78     { 79         insertSort(A, left, right); 80     } 81 } 82  83 void print(int A[], int n) 84 { 85     for(int i = 0; i < n; i ++) 86     { 87         cout<
       
        <<" "; 88     } 89     cout<
       
      

3）时间复杂度分析

对于N=5~20，采取插入排序更快，因为不需要递归的成本。

最坏情况下，枢纽元是最小元素，那么：

T(N) = T(N-1) + cN

T(N-1) = T(N-2) + c(N-1)

...

T(2) = T(1) + c*1

=>　　T(N) = T(1) + c(1+2+...+N) = O(N^2)

最好情况下，枢纽元刚好是数组的中值，那么数组刚好被分为两个均等的数组：

T(N) = 2T(N/2) + c*N

T(N)/N = T(N/2)/N/2  + c

...

T(2)/2 = T(1)/1 + c

T(N)/N = T(1)/1 + c*logN

所以，T(N) = N + c*N*logN = O(NlogN).

平均情况下，假设元素大小是等可能的，那么T(i) = (1/N)(T(1) + T(2) + ... + T(N-1))，那么：

T(N) = T(i) + T(N-i-1) + c*N = (2/N)(T(0) + T(1) + T(2) + ... + T(N-1)) + c*N.

令 sumN = T(1) + T(2) + ... + T(N-1)，则：

NT(N) = 2(T(0) + T(1) + T(2) + ... + T(N-1))+ c*(N^2)

(N-1)T(N-1) = 2(T(0) + T(1) + T(2) + ... + T(N-2)) + c*((N-1)^2)

所以，NT(N) - (N-1)T(N-1) = 2*T(N-1) + 2cN - c

...

T(N) = O(NlogN).