快速排序算法其实只做了两件事：寻找分割点（pivot）和交换数据。

    所谓寻找分割点，既找到一个预计会在中间位置附近的点，当然尽量越接近中点越好。

    所谓交换数据，就是把比这个分割点小的数据，最终都放在分割点左边，比它大的都放在右边。

    

    设要排序的数组是A[left]……A[right]，首先任意选取一个数据（一般算法：使用随机数选取一个区间内的数。 文艺算法：取A[left]、A[right]和A[rand()]的中值。 二笔算法：选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

快速排序的具体算法是：

1）设置两个变量i、j，排序开始的时候：i=left，j=left+1；

2）取关键数据和A[left]交换，赋值给key，即key=A[left]；

3）从j开始向后搜索，即由前开始向后搜索(j++)，找到第一个小于key的A[j]，将A[++i]和A[j]互换。

4）重复第3步，直到 j>right，此时循环结束

5）此时令 int q=i；在A[left]...A[q-1]和A[q+1]...A[right]上重复1-4过程直到递归结束。

    

    这样，我们就可以将它兑现为代码：

/** * The Quick Sort Algorithm by C++ * Average Time Cost: nlogn * Author: Zheng Chen / Arc001 * Copyright 2015 Xi'an University of Posts & Telecommunications */#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;long long ans = 0;void swap(int &a, int &b){    int c = a;    a = b;    b = c;}int partition(int A[],int l,int r){    int t = rand()%(r-l);	int x = A[l+t];	int i = l;	int j = l+1;	swap(A[l+t],A[l]);	for(;j<=r;j++){		if(A[j]<=x){			++i;			swap(A[i],A[j]);		}	}	swap(A[i],A[l]);	return i;}void Quick_Sort(int A[],int l,int r){    if(l
        
         >A[i];    Quick_Sort(A,0,9999);    for(i=0;i<10;i++)        cout<
         
          <<' ';    return 0;}
         
        
       
      
     
    

    现在我们来看一个问题：如何找出数组A中的第 k 小的元素？ (1<=k<=n)

    在笔者看来，至少有以下三种方法：

     比如我们可以分为两种情况：k>n/2时，问题化为找到第 n-k 大的元素。我们可以构造一个长度为 n-k 的数组，然后维持这个数组的单调性。这样每一个元素都可以进来数组“打擂”，找到合适的位置。到了最后我们取数组的首元素或者末元素（具体要看聪明的你选用递增还是递减），就是答案了。

    当k<=n/2时，也是同样的道理。

    很容易看到，这种算法的时间复杂度在O(n^2)，实在无法令人满意。

    但是，Can we do better?

    是的，我们可以通过维持一个堆来加速，由于堆的优秀的特性，我们可以把时间复杂度降低到O(nlogn)

    我们还可以先将这些元素排序，再取出A[k-1]即可，时间复杂度也是O(nlogn)。

    还是那个问题，Can we do better?

    可以。

    还记得快速排序的算法吗？我们进行一次partition操作后，我们的分割点(pivot)元素一定“归位”了。我们再比较分割点元素和待查找元素的大小，就可以舍去左边或右边部分，只看剩下那部分。可以证明，这种算法的平均时间复杂度为Θ(n)。

    我们可以很容易的将其兑现为代码：

/** * Find out the n th smallest number in an array. * Coursera : Algorithms: Design and Analysis, Part 1 by Tim Roughgarden * Average Time Cost : θ(n) * Worst Time Cost: O(n^2) when every time the smallest number was chosen. * * Author: Zheng Chen / Arclabs001 * Copyright 2015 Xi'an University of Posts & Telecommunications */#include 
    
     #include 
     
      #include 
      
       using namespace std;void swap(int &a, int &b){    int c = a;    a = b;    b = c;}int partition(int A[],int l,int r){    int t = rand()%(r-l);    int x = A[l+t];    int i = l;    int j = l+1;    swap(A[l+t],A[l]);    for(;j<=r;j++){	if(A[j]<=x){	    ++i;	    swap(A[i],A[j]);	}    }    swap(A[i],A[l]);    return i;}int Quick_Sort(int A[],int l,int r, int target){    if(target > r)        return -1;    if(l
       
        target)        	return Quick_Sort(A,l,q-1,target);        else        	return Quick_Sort(A,q+1,r,target);    }    else return A[l];}int main(){    int A[] = {3,4,6,1,5,9,2,8,7};    int n;    for(int i=0;i<9;i++)        cout<
        
         <<' ';    cout<
         
          >n;    cout<<"The "<
          
           <<"th largest number in the array is: "<
          
         
        
       
      
     
    

    

    进阶篇：

    但是，这种实现也有缺点：可能我们就是点背，每次选的元素，不是待排序元素的最小值、就是最大值。这样我们每次只能排除一个元素，而每次操作的代价都是O(n)，因此算法的最坏时间复杂度可能达到O(n^2)。

    还是那个问题，Can we do better?

    Yes.

    我们如果能让分割点在在数组中至少为 2n/3 大，且不大于 n/3 个元素（就是排序后的位置应该在中间的1/3），这样每次我们至少可以排除 n/3 个元素。T(n) <= T(2n/3) + O(n)，解得 T(n) = O(n)。

    那么，我们如何做到这点呢？

    这里有一个解法：

        1.我们准备 upper(n/5) 个长度为5的数组，把A中所有元素“装进去”。

        2.使用低级排序把它们分别排序，由于每次只有5个元素，因此低级排序更快。然后取每组第三个元素（中间元素）放到另一个数组Sub中。

        3.对长度为n/5的Sub数组，调用主算法查找第n/10大的数。

    

    可以证明，尽管可能看起来有些复杂，但是每次确实只需要O(n)的时间代价即可查找到适合的分割点、并至少能舍弃 n/3 个一定不符合条件的元素，达到我们对时间复杂度的需求。

    当然不能忘了代码实现：

/** * Deterministic Selection Algorithm in C++ * Below is the pseudo-code * Coursera : Algorithms: Design and Analysis, Part 1 by Tim Roughgarden * Time cost: O(n) * Author: Zheng Chen / Arclabs001 * Copyright 2015 Xi'an University of Posts & Telecommunications */#include 
    
     using namespace std;int Quick_Sort(int A[],int l,int r, int target);void swap(int &a, int &b){    int c = a;    a = b;    b = c;}void insersion_sort(int A[] , int len){	for(int j = 1; j
     
      0 && A[i] > key){			A[i+1] = A[i];			i--;		}		A[i+1] = key;	}}int ChoosePivot(int A[], int l, int r){	int size = r-l+1;	int sub_num = size/5 ;	int i, j, k=0;	int tmp[sub_num][5];	int Sub[sub_num];	for(i=0; i
      
        r)        return -1;    if(l
       
        target)        	return Quick_Sort(A,l,q-1,target);        else        	return Quick_Sort(A,q+1,r,target);    }    else return A[l];}int main(){    int A[] = {3,4,6,1,5,9,2,8,7};    int n;    for(int i=0;i<9;i++)        cout<
        
         <<' ';    cout<
         
          >n;    cout<<"The "<
          
           <<"th largest number in the array is: "<
           
            M    if (k <= length(L1))        return select(L1,k)    else if (k > length(L1)+length(L2))        return select(L3,k-length(L1)-length(L2))    else return M    } */
           
          
         
        
       
      
     
    

     本文参考资料：

         [1].Coursera : Algorithms: Design and Analysis, Part 1 by Tim Roughgarden   (斯坦福大学算法课)

         [2].《Introduction to Algorithms》 by  Thomas H. Cormen，Charles E. Leiserson，Ronald L. Rivest，Clifford Stein. Chapter 7, Quick Sort and Chapter 9, Medians and Order Statics.

        [3].ICS 161 : Design and Analysis of Algorithms. Lecture notes for Jan 30th, 1996.  http://www.ics.uci.edu/~eppstein/161/960130.html

        如果您觉得本文对您有些许帮助，欢迎收藏和转发本文！