快速排序

基本思想：

快速排序是基于分治策略的一种排序算法。选择一个基准元素，然后通过排序将数据分割成独立的三部分，其中一部分的所有数据比另一部分的所有数据都要小，中间为基本点。然后再按此方法分别递归对两部分进行排序，以达到整体有序的过程。

对于输入的数组a[p:r]按以下3个步骤进行排序：
1.分解：以a[q]为基准元素，将a[p:r]分为a[p:q-1],a[q],a[q+1:r]。其中a[p:q-1]中任何一个元素小于等于a[q],而a[q+1:r]中任何元素都大于等于a[q]。
2.递归求解：对a[p:q-1]和a[q+1:r]递归调用快速排序。
3.合并：由于对a[p:q-1]和a[q+1:r]的排序都是就地进行的，所以不需要额外执行任何操作，a[p:r]已排好序。

c++实现代码如下：

#include  <iostream>
using namespace std;
void qSort(int a[], int left, int right);
int main(){
  int num[20] = {3,2,3,5,9,87,56,32,12,3,3,3,3,2,4,5};
  int length = sizeof(num)/sizeof(int);
  for(int i = 0; i < length; i++){
        cout << num[i] << " " ;
        }
        cout << endl;
        qSort(num, 0, length-1);
  for(int k = 0; k < length; k++)
        cout << num[k] << " ";
        cout << endl;
  return 0;

}
void qSort(int a[], int left, int right){
        if(left < right){
              int i = left, j = right, x = a[left];
              while(i < j){
                while(i < j && a[j] >=x){ //从右往左找第一个小于x的数
                        j--;
                 }
                if(i<j) a[i++] = a[j];
                while( i < j && a[i] < x){ //从左往右找第一个大于x的数
                        i++;
                }
                if(i < j) a[j--] = a[i];
            }
           a[i] = x;
           qSort(a, left, i-1); //递归调用
           qSort(a, i+1, right);
   }
}

备注：

while(i < j && a[j] >=x)  while(i < j && a[j] <x) //这里有=取舍的问题。

参考：
C++快速排序