快速排序详解及优化
前言
本篇文章是排序算法系列的第三篇，学习快速排序
它在排序算法中非常的重要，这里单开一章，希望大家能完全的理解这种算法
因为，如果不看应用场景，对完全随机且散列的的数据进行排序，平均来看无疑快速排序是最快的
后面这段话将作为排序算法系列博客每一篇的开头：
为避免文中过多赘述，写在最前面：
- 接下来所有的排序算法讲解中，无论是思路梳理，还是代码实现，都是最终实现从小到大排序，从大到小可以学会后自行类推。
- 都是使用int数组进行排序，数据总量为n
快速排序
核心理念
快速排序整体思路是这样的：
- 首先在数组中随便找到一个数字，用它作为基准数字，或者叫分界值
- 将大于等于基准数字的放在基准数字右边，小于基准数字的放在基准数字左边
- 只要将左右两边当做两个新的数组，在新数组中至少有两个数字的情况下，再执行这三个步骤；
- 最终全部执行完毕后，数组就完成了排序
对于快速排序算法的核心理念，有人说是分治的思想，有人说是对递归的使用，也有人说把数组隔成两边的方法才是精髓...
众说纷纭，也各有各的道理，这里没办法对这个问题作出结论
下面我们用Java语言，逐步带大家实现快速排序，可以自行来感受一下快速排序的思想
实现思路
根据上面所说的快速排序思路，如果可以的话，大家能先尝试自己去实现这个思路，会对学习产生极大的帮助，笔者本人当初学习时就先带着自己的思考，自行实现了一下，在下边我们先带大家走进我当时的思路
自创移动法
理清思路不难看出，只要我们写一个方法，可以将数组用一个数组中的数作为分界，划分成左边都比他小，右边都比他大的两个数组，然后对左右两边递归的重新调用这个方法即可完成排序
那么怎么办到办到这种划分呢，一步一步来
首先需要选出一个数组中的数字作为基准数字
这里毕竟初次实现，不搞得太复杂，对于从数组中选出一个数字来说，最简单的无非就是选择第一个或者选择最后一个
那么就从选择第一个数字作为基准数字开始推进
这样我们只需要遍历第一个数字之后的所有数字，只要比第一个数字小，就把它放到基准数字前边，首先想到的是，按照插入排序中用到过的向前移动的方法，将它移动到基准数字的前面
最后返回基准数字的索引，调用的人就知道如何将数组划分为左右两边了
思路有了就用代码实现出来
/**
* 找一个数字作为基准p，让s数组中限定范围内，这个数左边都<p，右边都>=p
* 自己实现的时候思考出的:移动法
* 1.基准数字定为最左边
* 2.从左到右遍历，遇到小于基准数字的就移动到基准数字左边，直到遍历完成
* 3.中间持续记录基准数字移动后所在的位置索引
* @param arr 数组
* @param start 限定范围的起点
* @param end 限定范围的终点
* @return 基准数字所在位置的索引
*/
private static int partition(int[] arr, int start, int end) {
//2.用一个索引记录这个基准数字的位置,初始化就是起点索引
int index = start;
//3.将比这个数字小的都移动到左边（将left到这个数字中间的所有数据后移，将这个数字移动到原先left的位置）
// 首先外层循环，遍历left后的每一个元素，如果小于当前left就移动到left左边
for (int i = index+1; i <= end; i++) {
//判断如果满足移动条件，内层循环执行移动操作
if (arr[i]<arr[index]){
//临时变量记录下要移动的数据
int temp = arr[i];
for (int j = i-1; j >= index; j--) {
arr[j+1] = arr[j];
}
arr[index] = temp;
//进行后移操作后，基准数字的位置发生了改变
index ++;
}
}
return index;
}
再分析如何递归
递归还是要有一个分段的思想，要执行快速排序的一定是数组中的一段数据，所以需要知道起点和终点，以此来划定一个要做操作的数组范围，然后调用partition方法将这一段再划分为两段，再让划分出的两个数组作为新的需要执行快速排序的数组段调用再调用这个方法
/**
* 快速排序的思想，需要递归的对数组中某一部分进行排序
*
* @param arr 待排序数组
* @param start 本次要排序待排序数组，中一部分的，起点
* @param end 本次要排序待排序数组，中一部分的，终点
*/
private static void quickSort(int[] arr, int start, int end){
//1.找一个数字作为基准p，让这个数左边都<p，右边都>=p
int index = partition(arr, start, end);
//2.完成之后，比基准数字小都都在左边，大的都在右边，再重复对左右两边的部分进行上述操作
//3.考虑递归边界，判断如果左右边总数据量小于两个(0个或1个)就不再递归了
if (index-1-start>=1){
//左边就是从start到index-1
quickSort(arr,start,index-1);
}
if (end-index-1>=1){
//右边就是从index+1到end
quickSort(arr,index+1,end);
}
}
这样一整个快速排序好像是完成了，先用80个数据测试，发现排序结果是正确的
再用8w个数据测试，发现效率非常低，8w数据需要600+毫秒，相比较而言比插入排序还要稍慢一些
原因是什么呢，递归肯定没有问题，问题一定出在对按基准数字划分
分析了很久，发现移动的效率太低了，确实和插入排序几乎一样，甚至移动次数还要更多
这里，从左向右遍历找到比基准数字小的数后，完全没有必要一位一位挪过来，可以直接用两次交换就把它刚好放在基准数字左边一位
自创移动法改进：双交换法
1.首先将找到的待交换数字放在临时变量
2.将基准数字的后一个放到带交换数字的位置，将基准数字放到后一个，再将提前取出的待交换数字放在原来的基准数字位置
这样也可以达到之前一位一位移动过来的目的
/**
* 找一个数字作为基准p，让s数组中限定范围内，这个数左边都<p，右边都>=p
* 自己实现的时候思考出的移动法进行改进，这里称为：双交换法
* 1.基准数字定为最左边，用一个指针始终指向它
* 2.大循环从左到右遍历，遇到小于基准数字的
* a.先将这个数字和基准数字交换位置
* b.再将基准数字和原先位置的下一个交换
* c.记录基准数字移动后所在的位置索引
* d.简化一下，是将当前数字拿出来放在临时变量中，然后基准数字的后一个放在当前数字的位置，基准数字防止后一个，当前数字放在原来基准数字的位置
* 这样只需要对三个数字进行交换即可完成
* 3.大循环遍历结束后就完成了左右的划分
* @param arr 数组
* @param start 限定范围的起点
* @param end 限定范围的终点
* @return 基准数字所在位置的索引
*/
private static int partitionPlus(int[] arr, int start, int end) {
//2.用一个索引记录这个基准数字的位置,初始化就是起点索引
int index = start;
//3.将比这个数字小的都移动到左边（将left到这个数字中间的所有数据后移，将这个数字移动到原先left的位置）
// 首先外层循环，遍历left后的每一个元素，如果小于当前left就移动到left左边
for (int i = index+1; i <= end; i++) {
//判断如果当前数字比基准数字小，执行两次交换将它放在基准数字左边
if (arr[i]<arr[index]){
//临时变量记录下要移动的数据
int temp = arr[i];
arr[i] = arr[index+1];
arr[index+1] = arr[index];
arr[index] = temp;
index++;
}
}
return index;
}
经过改进，8w数字排序到了10毫秒左右
跟之前的希尔一样，不是说快速排序是最快的吗，重新执行了一遍希尔，15毫秒，发现是因为今天的电脑比之前测试希尔时慢......
此时心满意足的觉得自己成功实现了快速排序
于是去网上搜索了目前普遍的实现方式，递归部分没有任何区别
但实现划分数组的方法却又是和我的大相径庭
一遍代码读过去还没能看懂......
各种找帖子找博客，终于让我搞明白了主流的两种划分数字的方法
标准实现一：填坑法
/**
* 找一个数字作为基准p，让s数组中限定范围内，这个数左边都<p，右边都>=p
* 标准答案一：填坑法
* 1.基准数字定为最左边的数字，定义左右两个指针，一个指向最左边，一个指向最右边
* 2.将基准数字挖出来作为一个坑，最开始坑在最左边
* 3.如果左指针还在右指针的左边，就进入一个循环
* a.循环中第一个操作：
* 从右指针出发到左指针结束，找一个小于基准数字的数据
* 一种情况是找到了，一种情况是一直到左指针的后一个都没有找到
* 如果找到了就执行填坑进行后续从左到右的操作
* 如果没找到说明已经按要求排列好了，退出大循环即可
* b.循环中第二个操作：
* 从左指针出发到右指针结束，找一个大于基准数字的数据
* 同上两种情况
* 4.所有如果还要进行下一次大循环，坑的位置还是在左指针，即循环中先执行从右到左
* 5.最终大循环结束后表示left==right，就是基准数字应该在的位置，将基准数字安插在这里
* 6.返回left或right都行，就是基准数字的索引位置
*
* @param arr 数组
* @param start 限定范围的起点
* @param end 限定范围的终点
* @return 基准数字所在位置的索引
*/
private static int partition2(int[] arr, int start, int end) {
//1.指定第一个数为基准数字，将基准数字挖出来存在这里，原来的位置当做一个坑用于排序
int p = arr[start];
//2.定义两个指针，一个在最左边，一个最右边
int left = start;
int right = end;
//3.只要左指针还在右指针的左边，就循环用右边找一个小于p的填左边坑，右边作为新坑，再从左边找一个>=p的填右边的坑
while (left<right){
//进入循环坑一定在左边，所以先从右向左
//先从右到左寻找比基准数字小的，找到就让右指针指向这个数字
while (left<right && arr[right] >= p){
right--;
}
//退出从右到左的寻找循环表示找到了，或者left=right了
if (left==right){
//说明排好了
break;
}
//到这里没有退出循环说明找到了，用它填左边的坑，再将左指针后移，此时右指针位置变成新坑
arr[left] = arr[right];
left++;
//再从左到右寻找比基准数字大的，找到就让左指针指向这个数字
while (left<right && arr[left] < p){
left++;
}
//退出从左到右的寻找循环表示找到了或者left==right了
if (left==right){
//说明排好了
break;
}
//到这里没有退出循环说明找到了，用它填右边的坑，再将右指针前移，此时左指针位置变成新坑
arr[right] = arr[left];
right--;
}
//直到退出大循环，此时的left一定等于right，就是基准数字应该在的位置，将基准数字安插在这里
arr[left] = p;
//返回基准数字所在位置索引
return left;
}
标准实现二：交换法
/**
* 找一个数字作为基准p，让s数组中限定范围内，这个数左边都<p，右边都>=p
* 标准答案二：交换法
* 1.基准数字定为最左边的数字，定义左右两个指针，左指针指向基准数字后一个，右指针指向最右边
* 2.保持一个循环一遍一遍尝试交换（从哪个方向开始都可以，逻辑会变）
* a.循环中第一个操作：
* 从左指针到右指针进行扫描（不用扫描右指针以及之后的数据）
* 寻找一个大于基准数字的数据找到就指向它
* 最终如果找不到会指向右指针的位置
* b.循环中第二个操作：
* 从右指针向左进行扫描（如果找不到需要一直扫描到基准数字为止）
* 寻找一个小于等于基准数字的数据，找到就指向它
* 不用判断边界，就算中间找不到基准数字自己就是小于等于基准数字的
* c.两个内层扫描结束后，有两种情况
* （1）两指针交错前两边都找到了
* 这种情况就交换两个指针的数据，再去下一次循环
* （2）两指针交错后两边才找到
* 这种情况说明当前right指针是最后一个小于基准数字的
* 将基准数字和right交换就排好了，直接返回right就是基准数字位置索引
*
* @param arr 数组
* @param start 限定范围的起点
* @param end 限定范围的终点
* @return 基准数字所在位置的索引
*/
private static int partition3(int[] arr, int start, int end) {
//1.指定第一个数为基准数字，将基准数字挖出来存在这里，原来的位置当做一个坑用于排序
int p = arr[start];
//2.定义两个指针，一个在基准数的下一个，一个在最右边，用于左到右和右到左的扫描
int left = start+1;
int right = end;
//3.保持一个循环，再循环中判断排好，直接用返回结束循环
while (true){
//这里先左到右或先右到左都可以
//先从左指针开始向右指针扫描（不用扫右指针及右指针之后的）,直到发现一个大于基准数字的就指向它
while (left < right && arr[left] <= p){
left++;
}
//再从右指针开始向左扫描（需要扫左指针及左指针之后的），直到发现一个小于等于基准数字的就指向他
while (arr[right] > p){
right--;
}
//这里有两种情况需要区别对待，如果right>left，说明两个指针交错前两边都找到了，两个数据进行交换
if (right>left){
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
//否则说明两边交错后才找到，此时交换基准数字和right就排好了,返回基准数字索引right
else {
int temp = arr[start];
arr[start] = arr[right];
arr[right] = temp;
return right;
}
}
}
测试对比
实现思路中一共写了四种实现，首先经测试，排序结果都是正确的
下面我们来进行一下效率对比
分别进行800w数据排序五次，8000w数据排序3次
移动法：这明显是残次品，太拉垮了，不参与对比
双交换法：884、873、905、887、873——9633、9361、9541
填坑法：824、789、783、769、800——8847、8151、8414
交换法：855、819、833、829、800——8610、8990、8953
结论：有差距但不是特别大，填坑法略优于交换法略优于自创的双交换法
快速排序优化思路
我们来分析一下，上文实现的快速排序还有哪些可以优化的地方
首先还是从分析快速排序一些坏的的情况出发
1.优化基准数字选择
假如快速排序每次选取到的都是数组中的最大值，对于以第一个数作为基准数字来说就是刚好逆序，它每次需要将所有右侧的数据都移动到左侧，几乎沦为冒泡排序
那么每次寻找基准数字时，如果他能更趋近于中位数，效率会增加
但是找中位数需要用到的算法也很麻烦，得不偿失，最后能更简单的找一下就可以
一般采用三数取中的方式来进行优化
找到数组第一个、中间一个和最后一个数字，三个数字排序后取中间的数据作为基准数字
我们可以将找到的数字放到第一个位置，这样可以不用改变后续的分割函数
2.优化重复数据的处理
待排序数组中如果有大量重复数据，也会存在优化空间
这种情况还不少见，比如今年2022年高考考生人数1193w，如果对按成绩排名，总共750分，必然出现大量重复
但因为之前的算法中数组分割后，右边数组中可能还存在等于基准数字的数字，他在后续的排序中可能还需要被移动很多次，如果我们在分割时将重复数字聚集在一起不再分割，共同作为基准数字，效率也会增加
3.数据量小时采用插入排序
根据统计，随着数据量的减小，快速排序的递归行为产生的额外性能开销会逐渐盖过算法带来的性能优势，此时插入排序会比快速排序更快。数据量小到什么程度使用插入排序比较好呢，笔者没有进行过测试，但是阅读jdk源码中Arrays.sort()方法发现，这个方法中当数组长度小于47就会使用插入排序，想必应该是测试过得出具有普适性的结论，数据量小于47时，插入排序的效率是最高的。
强化练习
根据优化思路，实现一个优化后的快速排序
可评论留言获得强化练习代码（含详细注释讲解）
总结
在前言中我们提到—— 对完全随机且散列的的数据进行排序，平均来看无疑快速排序是最快的
但是通过优化分析发现，实际上还有优化空间，那些慢的排序算法也有优点，快的排序算法也有缺点，如果能结合他们的优缺点，还能优化出更快的排序算法
比如我们分析了jdk源码中Arrays.sort()，就不是一个简单的排序，而是结合了很多的东西，如果继续往下读还会发现它还使用到了一种本系列还没有提到的算法—— 归并排序
本文到这里就结束了，下一篇我们会来讲解这个新的排序算法，归并排序
等大家全部理解了插入、快速、归并三种算法后，就具备了阅读Arrays.sort()源码的资本（读源码新手没人带看，先不要去管泛型数组和Object数组的排序，简单一点只去看int数组排序就好），可自行阅读试试，也可以等后续我来带大家解读jdk中排序的实现
