快速排序是我们经常用到的一种排序算法，它相比与 冒泡排序，时间的复杂度更小，速度更快，排序采用了二分的思想。 快速排序的思想：从序列的两端开始“探测”，首先得找一个基准A(一般是从左边找)，用两个变量i、j分别指向序列的最左边和最右边，然后先移动j，先从右往左找到一个比A小的数，然后再移动i,从左往右找一个大于A的数，然后交换他们，然后j继续向左挪动（如果基准是左边第一个的话，必须j先移动），找比基准小的数，找到后，i继续向右挪动，重复上述操作，直到i和j相遇了，此时，执行最后的步骤：将基准的数，和相遇位置下标下的值 交换。当然这只是第一轮的结束，然后第一轮结束后，序列被划分为两部分：比基准小的在左边，比基准大的在右边，然后继续对这两部分序列进行上述的排序操作，直到两边都排好顺序，这样快速排序才结束。 因为快速排序是不断地对序列划分，再排序的，因此需要利用递归来实现。 各种排序的算法的时间复杂度如图： 快速排序的具体操作步骤如下： 1：从左边随便找一个基数（为了方便，就找最左边的那个） 2：然后最左边的那个下标记作i ，最右边的记作j ，然后，从右边找到一个比 之前那个基数小的数， 记录那个数的下标，然后，从左边找到一个比之前 那个基数大的数，同样的，记录它的下标。 3：交换这两个数； 4：重复2，和3 操作，直到i==j ，然后让第一个数 和 第i个数 交换； 不断重复上述过程，直至最后 完成了两个数之间的排序，则排序完成。 具体实现代码如下：
#include<iostream> #include<cstring> #include <set> #include <map> #include <ctime> #include <bitset> #include <sstream> #include <algorithm> #include<math.h> #include<stdio.h> #include<stdlib.h> #include<conio.h>//getch()的头文件 #include<vector> #include<queue> #include<stack> using namespace std; int a[100],n;//定义全局变量，这两个变量需要在子函数中使用 void quicksort(int left,int right) { int i,j,t,temp; if(left>=right) //快速排序的终止条件 return; temp=a[left]; //temp中存的就是基准数 i=left; j=right; while(i!=j||i<j) { //顺序很重要，要先从右往左找 while(a[j]>=temp && i<j) //i必须小于j j--; //再从左往右找 while(a[i]<=temp && i<j) //i必须小于j i++; //交换两个数在数组中的位置 if(i<j)//当i,j没有相遇时 { t=a[i]; a[i]=a[j]; a[j]=t; } } a[left]=a[i]; //i==j 或者 i>j的时候(最后两两比较 就会出现 i >j),交换位置 a[i]=temp; quicksort(left,i-1);//继续处理左边的，这里是一个递归的过程 quicksort(i+1,right);//继续处理右边的，这里是一个递归的过程 } int main() { int i,j,t; //读入数据 scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); quicksort(1,n); //快速排序调用 //输出排序后的结果 for(i=1;i<=n;i++) printf("%d ",a[i]); return 0; }注意：步骤2 必须要从右边开始找，否则会出错，为什么呢？ 举个例子 比如 一组数 为 6 1 2 7 9 ，如果我们先从左边找，找一个比6大的数值，那么这个数值是7 然后，我们再从右边找一个比6小的数，因为 循环里的条件为：while(a[j]>=temp(基准数的值)&& i<j) j–; // 所以，如果从9开始找的话，那么，j最终会 停留在7上（此时 i==j ，不满足i<j ) 所以会跳出循环，执行循环外的代码：将基准数跟这个 i= = j的 位置的数值交换 ，最终第一轮排序后的结果是: 7 1 2 6 9 ，然后 就 不符合我们快速排序的要求：基准左边的数都比基准小，基准右边的数都比基准大。
我们第一轮排序需要的结果是：2 1 6 7 9 这才能保证，6 左边的所有数字 都 比6小，然后 右边的数字都比6大，这才符合快速排序的思想与要求。 因此，快速排序 要先从右边开始找一个比基准大的数，当然，从右边找是因为基准一般是左边的第一个（如果基准在右边的话，当然可以反过来操作：即可以在左边找大的，右边找小的）
