快速排序算法：
最主要的地方就是确定"枢轴"
假设一个数组：{2,5,6,4,3,8,9,1,7,0}需要排序
我们可以选左边的数或右边的数作为枢轴
排序的时候：
在左边找一个大的，右边找一个小的，交换位置
第一次：把小于枢轴的数放左边，大的放右边，这里选枢轴为2，
排序完为{1,0,2,4,3,8,9,6,7,5}
|
第二次：2的位置固定了，然后以2为分界线
对2的左边：选枢轴，小的放左边，大的放右边，这里选枢轴为1，
排序完为{0,1,2,4,3,8,9,6,7,5}
对2的右边：选枢轴，小的放左边，大的放右边，这里选枢轴为4，
排序完为{0,1,2,3,4,8,9,6,7,5}
| |
第三次：1的位置和4的位置也固定了，然后分别以1和4为分界线
1的左边：已经排好。1的右边到2：已经排好
4的左边到2：已经排好；
4的右边：选枢轴，小的放左边，大的放右边，这里选枢轴为8，
排序完为{0,1,2,3,4,7,5,6,8,9}
第四次：
8的左边到4：这里选枢轴为7，
排序完为{0,1,2,3,4,6,5,7,8,9}
8的右边：已排好
第五次：
7的左边到4：这里选枢轴为6，
排序完为{0,1,2,3,4,5,6,7,8,9}
7的右边：已排好
结束
此排序使用递归实现
1 #include<iostream> 2 3 using namespace std; 4 int n=0; 5 //函数模板 6 template<class T>//对任何数据类型都可以排序 7 void QuickSort(T *a,const int left,const int right) 8 { 9 if(left<right) 10 { 11 //选枢轴划分 12 int i = left; 13 int j = right+1;//表示多加的那个数，能让下面的判断条件简单一些，能提高些速度 14 int pivot = a[left];//选左边的为枢轴 15 16 do{ 17 do i++; 18 while(a[i]<pivot); 19 do j--; 20 while(a[j]>pivot);//在左边找一个大的，右边找一个小的，交换位置 21 if(i<j) swap(a[i],a[j]); 22 }while(i<j); 23 swap(a[left],a[j]);//把枢轴放到中间去，j为中间 24 25 n++; 26 cout<<"第"<<n<<"次排序："<<endl; 27 for(int k=0;k<10;k++) 28 cout<<a[k]<<" "; 29 cout<<endl; 30 31 QuickSort(a,left,j-1);//左半边 32 QuickSort(a,j+1,right);//右半边 33 34 35 36 } 37 } 38 39 40 int main() 41 { 42 int k[]={2,5,6,4,3,8,9,1,7,0,9999};//最后一个数不参与排序，故意加的，但要比前面的数大 43 QuickSort(k,0,9);//0是左下标，9是右下标 44 cout<<"最后结果为："<<endl; 45 for(int i=0;i<10;i++) 46 cout<<k[i]<<" "; 47 cout<<endl; 48 system("pause"); 49 return 0; 50 } 51
