目录
疑问：这里可能人小伙伴会问，递归时 j 能改为 i 吗，这是是可以的，对称就可以，但是此时分界点就不能设置为q[ l ]，可以是q[ (l + r) / 2]，也可为去q[ r ]
前言
上一篇文章，我们学习了冒泡排序的思路，有疑惑的可以阅读以下我的上一篇文章
(4条消息) ＜C语言＞你真的想明白冒泡排序了吗？_prodigy623的博客-CSDN博客
而选择排序法和冒泡排序只是众多排序方法中的两种，本篇将介绍分治法快速排序。
一、分治法是什么意思？
分治法(Divide and Conquer)的基本思想是将一个规模较大的问题分解为若干规模较小的子问题，找出各子问题的解，然后把各部分的解组合成整个问题的解。因此
- 分治法的分(Divide)是指：划分一个大问题为若干个较小的子问题；
- 治(Conquer)就是：分别解决子问题(最基本的问题除外)，并从子问题的解构建原问题的解。
如果在排序中应用分治法，可以有两种思路：
(1)选择一个基准元素，将待排序数列分为比基准元素小的一组和大的一组数列，然后再分别对这两组数列排序，最后再直接合并两组排序的结果。这就是著名的快速排序法(Quick Sorting)。
(2)将待排序数列等分为两组，分别对这两组数列排序，最后再合并两组排序后的结果。这就是归并排序法(Merge Sorting)。
二、实现分治-快速排序法思路
1.确定分界点
在数组中，我们可随机确定一个元素为分界点，将整个数组划分为小于等于x的数组1 和 大于等于x的数组2，这个分界点一般为数组 第一个元素q[ l ]、数组最中间元素q[ ( l + r) / 2 ]、数组最后一个元素q[ r ] 或 随机一个元素。
2.调整范围
这一步是整个算法最核心的一步，将小于等于x的元素全放至x的一侧，将大于等于x的元素全放至x的另一侧
2.1 暴力法
1.定义两个数组 a[ ]，b[ ]
2.遍历数组 q[ l ~ r ]
- 将小于等于x的元素放置数组 a[ ]中
- 将大于等于x的元素防止数组 b[ ]中
3.再依次将a[ ]数组放置q[ ]、b[ ]数组放置q[ ]
这里开辟了额外的空间a[ ]、b[ ]
2.2 优雅而简洁的的指针法
- 用两个指针 i , j 分别指向最左边元素、最右边元素
- 从 i 开始，将i指向的元素与 x 比较大小，若 *i < x 则 i++，直到遇见 *i >= x，指针 i 停止右移
- 然后从 j 开始，将 j 指向的元素与 x 比较大小，若 *j > x 则 j--，直到遇见 *j<=x，指针 j 停止左移
- 随后交换 i 与 j 所指向的元素，并且i++，j--，直到两指针相遇或交错，这样在指针 i 左边的元素都小于等于x，在指针 j 右边的元素都大于等于x，像这样不需要开辟空间就完成了数组内大小的调整
例如： 2 1 3 4 5
取x = q[ l ] = 2
第一步判断 i 指向的元素2是否大于2，否，指针 i 停止
第二步判断 j 指向的元素5是否大于2，是，指针 j 左移一次指向4
4大于2继续左移，指向3，
3大于2，继续左移指向1，1不大于2，指针 j 停止移动
第三步指针 i 与 j 交换各自指向的元素，i++，j--，指针相错停止循环
此时 i 左边指向的数都小于等于2，j 右边的数都大于等于2
3. 递归处理左右两段
将左右两端数组递归上述过程，直至每个数组元素都只剩一个元素，这里就是分治法的分，划分一个大问题为若干个较小的子问题，最终合并
三.代码实现
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N];
void quick_sort(int q[], int l, int r)
{
if (l >= r)
{
return;
}
int x = q[l], i = l - 1, j = r + 1;//这里将i与l都向外移动一次，是因为后续循环不管三七二十一就要移动一次
//所以事先移动一次，后续才能循环移动时指针真的指向边界
while (i < j)//这里循环迭代交换数值
{
do
{
i++;//这就是上述事先移动的原因
} while (q[i] < x);
do
{
j--;
} while (q[j] > x);
if (i < j)
{
int tmp = q[i];
q[i] = q[j];
q[j] = tmp; //完成交换
}
}
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;
}疑问：这里可能人小伙伴会问，递归时 j 能改为 i 吗？
答案：这是可以的，对称就可以，但是此时分界点就不能设置为q[ l ]，可以是q[ (l + r) / 2]，也可为去q[ r ]
int x = q[r], i = l - 1, j = r + 1;//这里将i与l都向外移动一次，是因为后续循环不管三七二十一就要移动一次 //所以事先移动一次，后续才能循环移动时指针真的指向边界
while (i < j) //这里循环迭代交换数值
{
do i++; while (q[i] < x);//这就是上述事先移动的原因
do j--; while (q[j] > x);
if (i < j)
{
int tmp = q[i];
q[i] = q[j];
q[j] = tmp; //完成交换
}
}
quick_sort(q, l, i - 1);//第三步递归，完成分治法的分
quick_sort(q, j, r);
为什么分界点不能为q[ l ]呢？
因为这里会出现边界问题，例如：我要排序1，2两个元素，将q[ l ]作为分界点
经过循环i与j相遇，同时指向1，i=j=0，关键在递归传参时第一个递归范围是【0，-1】，不进行递归，第二个递归范围是【0，1】进行递归出来的范围还是【0，1】，我们发现它进行了无限递归，栈溢出程序崩溃，同理当递归参数为 i 时，分界点不能为q[ r ]，因为也可能发生无限递归。
总结
像这样的对于下标具有边界问题，建议背过一个模板（经过千锤百炼检验过的），记住一个就可以，以防测试时没时间再考虑边界而出现问题。
新手上路，请多关照。有什么问题也可以在评论区留言，或者私信我哦，觉得对您有帮助的话还请三连支持哦。算法虐我千百遍，我对算法如初恋。