快速排序（quick-Sort）
是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
算法介绍
设要排序的数组是$A[0]……A[N-1]$，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
一趟快速排序的算法是：
1）设置两个变量$i$、$j$，排序开始的时候：$i=0$，$j=N-1$；
2）以第一个数组元素作为关键数据，赋值给$key$，即$key=A[0]$；
3）从$j$开始向前搜索，即由后开始向前搜索 $j–$，找到第一个小于$key$的值$A[j]$，将$A[j]$和$A[i]$互换；
4）从$i$开始向后搜索，即由前开始向后搜索 $i++$，找到第一个大于$key$的$A[i]$，将$A[i]$和$A[j]$互换；
5）重复第$3$、$4$步，直到$i=j$； ($3$,$4$步中，没找到符合条件的值，即$3$中$A[j]$不小于$key$,$4$中$A[i]$不大于$key$的时候改变$j$、$i$的值，使得$j=j-1$，$i=i+1$，直至找到为止。找到符合条件的值，进行交换的时候$i$，$ j$指针位置不变。另外，$i==j$这一过程一定正好是 $i++$或 $j–$完成的时候，此时令循环结束）。
排序演示
示例
假设用户输入了如下数组：
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 数据 | 6 | 2 | 7 | 3 | 8 | 9 |
创建变量 $i=0$（指向第一个数据）, $j=5$(指向最后一个数据), $k=6$(赋值为第一个数据的值)。
我们要把所有比$k$小的数移动到$k$的左面，所以我们可以开始寻找比$6$小的数，从$j$开始，从右往左找，不断递减变量$j$的值，我们找到第一个下标$3$的数据比$6$小，于是把数据$3$移到下标$0$的位置，把下标$0$的数据$6$移到下标$3$，完成第一次比较：
|下标|0|1|2|3|4|5|
|-
|数据|3|2|7|6|8|9
$i=0$ , $j=3$ , $k=6$
接着，开始第二次比较，这次要变成找比$k$大的了，而且要从前往后找了。递加变量$i$，发现下标$2$的数据是第一个比$k$大的，于是用下标$2$的数据$7$和$j$指向的下标$3$的数据的$6$做交换，数据状态变成下表：
|下标|0|1|2|3|4|5|
|-
|数据|3|2|6|7|8|9|
$i=2$ , $j=3$ , $k=6$
称上面两次比较为一个循环。
接着，再递减变量$j$，不断重复进行上面的循环比较。
在本例中，我们进行一次循环，就发现$i$和$j$ “碰头”了：他们都指向了下标$2$。于是，第一遍比较结束。得到结果如下，凡是$k(=6)$左边的数都比它小，凡是$k$右边的数都比它大：
|下标|0|1|2|3|4|5|
|-
|数据|3|2|6|7|8|9|
如果$i$和$j$没有碰头的话，就递加i找大的，还没有，就再递减$j$找小的，如此反复，不断循环。注意判断和寻找是同时进行的。
然后，对$k$两边的数据，再分组分别进行上述的过程，直到不能再分组为止。
注意：第一遍快速排序不会直接得到最终结果，只会把比$k$大和比$k$小的数分到$k$的两边。为了得到最后结果，需要再次对下标$2$两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。
调用函数
在c++中可以用函数qsort（）可以直接为数组进行排序。 [^2]
用 法:
void qsort(void base, int nelem, int width, int (fcmp)(const void *,const void *));
参数：
1 待排序数组首地址
2 数组中待排序元素数量
3 各元素的占用空间大小
4 指向函数的指针，用于确定排序的顺序
[^2]:反正这里是用C语言的，C++拿来拓展一下 >…<
源代码+注释
#include<cstdio>
#include<cstring> //字符串头文件
int a[1000001];
void quick(int left,int right)
{
if(left>=right) //如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了
return ;
int i=left; //将区间记录下来
int j=right;
int key=a[i]; //记录参考值
while(i<j) //控制在当组内寻找一遍
{
while(i<j&&key<=a[j]) //而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升序还是降序）2，没有符合条件1的，并且i与j的大小没有反转
j--; //向前寻找
a[i]=a[j]; //找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是a[left]，那么就是给key）
while(i<j&&key>=a[i]) //这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反
i++;
a[j]=a[i];
}
a[i]=key; //当在当组内找完一遍以后就把中间数key回归
quick(left,i-1); //最后用同样的方式对分出来的左边的小组进行同上的做法
quick(i+1,right); //用同样的方式对分出来的右边的小组进行同上的做法
//当然最后可能会出现很多分左右，直到每一组的i = j 为止
}
int main()
{
int n,m;
memset(a,0,sizeof(a)); //清空数组
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
quick(0,n); //引用函数
for(int ii=1;ii<n;ii++)
printf("%d ",a[ii]);
printf("%d\n",a[ii]);
}
return 0;
}ps.其实我们用个STL库直接调用sort函数就完事了，谁还学这个啊
希望大家喜欢这篇文章！！！
如有问题请留言，谢谢！！！
