快速排序相比冒泡排序快的多，而且还不浪费空间。众所周知冒泡排序的时间复杂度为O(N^2)，而快速排序平均时间复杂度为O(N ln N)。 所以快速排序是每个初学者必须掌握的基础排序算法。
快速排序的核心是确定一个参照数(基准数)，然后将别的数与参照数(基准数)相比较，将比它大的数放在它分右边，比它小的放右边，而与它相等的数则两边都可以放。以上是基本操作。
接下来我将具体解释。 假设我们有一串未排序的数： 6 1 2 7 9 3 4 5 10 8 我们以6为参照数，最后的要的出的结果为： 3 1 2 5 4 6 9 7 10 8 此时已经满座参照数两边的大小关系。 如何实现以上步骤： 1.参照数(基准数)一般以最左边的数来担当。 2.我们需要两个mark–n,m，分别从两边来找相应的数。 其中m从右向左（小于基准数的数），n从左向右（找大于基准数的数）。当m！=n时将两者的数值交换。 3，当m=n时，结束二过程，将基准数放到a[m]处，将原来的数放到基准数的初始位置。 如上将6放到了原来3的位置，3到了原来6的位置。 代码如下
int a[100]; void quicksort(int left,int right) { int n,m,t,temp; temp=a[left];\\确定基准数位数组第一个数 n=left; m=right;\\两个mark； while(i!=j) { \\mark查找元素必须先从右向左 while(n<m&&a[m]<=temp) j++; \\从左向右 while(n<m&&a[n]>=temp) n++; \\顺序不能颠倒 if(n<m) { t=a[n]； a[n]=a[m]; a[m]=t; } } a[left]=a[n]; a[n]=temp; } 如上代码就是实现一道排序工作。 6 1 2 7 9 3 4 5 10 8 3 1 2 5 4 6 9 7 10 8 2 1 3 5 4 6 9 7 10 8 1 2 3 5 4 6 9 7 10 8 1 2 3 5 4 6 9 7 10 8 1 2 3 4 5 6 9 7 10 8 1 2 3 4 5 6 9 7 10 8 1 2 3 4 5 6 8 7 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 看这个，将数以原基准数分割，把它分成两端，在以每段最左的数为基准数。重复上面的2，3步骤，quick sort函数。 因此需要用递归将问题一点一点变小。 只需要在函数quicksort最后加上 ```cpp quicksort(left,n-1); quicksort(n+1,right); 最后在主函数中调用它； 具体代码如下： #include<iostream> using namespace std; int a[101]; void quicksort(int left,int right) { int n,m,t,temp; if(left>right) return; temp=a[left]; n=left; m=right; while(n!=m) { while(m>n&&a[m]>=temp) m--; while(m>n&&a[n]<=temp) n++; if(m>n) { t=a[n]; a[n]=a[m]; a[m]=t; } } a[left]=a[m]; a[m]=temp; quicksort(left,n-1);//左边排序 quicksort(n+1,right);//右边排序 } int main() { int n; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } quicksort(1,n); for(int i=1;i<=n;i++) { cout<<a[i]<<" "; } return 0; }对于为啥要先从右向左，具体参考；转到
