从零开始的算法之路
——基础算法之快速排序
有了sort函数为什么还要学习其他的排序，的确也看起来比较多余（就目前来看我做的排序题都能用sort解决），但是里面算法中的思想才是我们应该重要去理解的
- 快熟排序的思路
不多说上图。
第一步：取基准数
第二步：分区进行排序
第三步：对两个区间递归进行分区间操作。
。
也就是说看完图解我们可以将快排总结为：
- 确定分界点，可以是q[l],q[r],q[(l+r)/2]，就是起点，终点或者是中间值。
- 调整区间，就是说要用分界点来进行左右的排序，比如左边的就排比分界点小的，右边排大的。
- 开始进行递归排序，就是左半边还要递归，右边也是进行递归，不断的区分成更小的区间，在更小区间处理后，在返回到更大的区间，这个就是分治的思想，下一话的归并排序也是需要用到分治的思想。
接下来是代码的实现。
我在这里就是实现的是函数部分。
void quick_sort(int q[],int l,int r)//l代表的是起点，r代表的是终点，在这里由于是需要一个递归处理，所以不能单纯的用一次双指针来搜索，需要把每次的起点和终点给弄出来，所以在这里是l，r。
{
if(l>=r) return;//如果起点大于等于终点就返回，就不用进行下去
int i = l-1.j = r+1,x = q[(l+r)/2];//看到后面就知道为什么是i-1，r+1,，一个是从前往后面搜，一个是从后往前搜，想当于是一个双指针算法。
while(i<j)//两指针相遇相当于搜完。
{
do i++;while(q[i]<x); //左半边小于自己规定的值，就要继续循环，如果找到大于的值，那么就先停下。
do j--;while(q[j]>x); //右半边大于自己规定的值，就要继续循环，如果找到小于的值，那么就停下。
if(i<j) swap(q[i],q[j]);//现在是找到了两个不符合条件的数字，那么就要进行交换。
else break;//否则就可以直接跳出循环。
}
quick_sort(q,l,j);//这个时候j已经走到了中间，就要进行函数的递归，所以是进行了一个左边的递归和右边的递归。
quick_sort(q,j+1,r);
}
标签：sort,递归,int,博客,quick,一号,区间,排序 From： https://www.cnblogs.com/iolzyy/p/17081000.html