浅谈快速排序思想（配合代码讲解）
分治法，分而治之，充分理解分治法是运用好快速排序的关键
快速排序的分治策略是：
（1）划分：选定一个记录作为轴值，以轴值为基准将整个序列划分为两个子序列 r1 … ri-1 和 ri+1 … rn，前一个子序列中记录的值均小于或等于轴值，后一个子序列中记录的值均大于或等于轴值；
（2）求解子问题：分别对划分后的每一个子序列递归处理；
（3）合并：由于对子序列 r1 … ri-1 和 ri+1 … rn 的排序是就地进行的，所以合并不需要执行任何操作。
一次划分过程
这里借用清华大学出版社的一次划分示意图中的内容来进行讲解
从上图的过程中可以看出，每次排序，选定第一个数为此次排序的轴值，每一次排序的目的就是将选定的这个数字，放到属于他的合适的位置，这个合适的位置是指：它前边的数全部小于它，后面的数全部大于它
之后就是一个递归的过程，分别处理两端，直至处理完成
同样引用清华大学出版社的快速排序示意图进行讲解
下面是代码讲解（详细注释表明在代码中）
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
//定义一些全局变量 在主函数以及函数中都可以使用
int n;
const int N = 1e6+10;
int q[N];
void quick_sort(int q[],int l,int r) {
if(l >= r) return;//如果左边界大于或者等于右边界 要么输入错误 要么只有一个数
int x = q[l + r >> 1];//设置每次排序的中间数作为轴值
int i = l-1;//因为我们每次都是 先移动再比较 所以第一次移动的时候我们需要把边界扩大一格
int j = r+1;//同理
while(i<j) {
do i++; while(q[i] < x);//若左边的值小于x i一直向右移
do j--; while(q[j] > x);//若右边的值大于x j一直向左移
if(i < j) swap(q[i],q[j]);//如果停下 说明要交换啦 swap交换函数
}
//对上述提到的轴值两边分别进行快速排序
quick_sort(q, l, j);
quick_sort(q, j+1, r);
}
//主函数
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);//读入数据
quick_sort(q,0,n-1);//使用快速排序函数
for (int i = 0; i < n; i ++ ) printf("%d ",q[i]);//写出数据
return 0;
}