排序算法----快速排序遇坑史
本帖最后由 逸帅 于 2021-3-23 00:05 编辑# 1、项目场景：
记录一次快速排序遇坑史，周围的室友、朋友不会数据结构和算法...
无奈，今天大部分时间都在快速排序上面了
# 2、问题描述：
1.快速排序传值的左边索引和右边索引一直是变化的，没理解怎么变化的
2.使用了递归，递归没有加return
# 3、原因分析：
1. 每次递归的左边索引和右边索引都是变化的，每次排序后，中轴值的索引，是左边元素的最右边索引，是右边元素最左边的索引，但是左边元素的左边索引，还是上次排序的左边索引，右边元素的右边索引，还是上次排序的右边索引。
也就是说，下一次还要用到上一次的左边索引和右边索引，所以要保留这两个索引
例如：
第一次:左边索引是0，右边索引是length-1，中轴值假设是center，排序后，中轴值左边的元素数组称为左数组，右边的元素数组称为右数组
第二次:左数组的左边索引还是0，但是右边索引是center-1，右数组的右边索引是length-1，左边索引是center+1
以此类推，所以左边的索引和右边的索引，每次都需要传值进去，因为一直在变化。
# 4、解决方案：
1、将左边的索引和右边的索引分别赋值给一个新的变量
```java
public static void quickSort(int[] initial, int left, int right) {
int leftIndex = left;
int rightIndex = right;
//取第一个数做中轴值
int center = initial;
```
2、添加结束递归的条件
```java
public static void quickSort(int[] initial, int left, int right) {
//当达到结束的条件，结束递归
if (left >= right){
return;
}
```
# 5、完整的代码：
```java
package com.yishuai.sort;
import java.util.Arrays;
/**
* @AuThor yishuai
* @description 快速排序算法
* @date 2021/3/22 9:02 下午
*/
public class Quick {
public static void main(String[] args) {
int[] initial = {5, 9, 2, 8, 6, 3, 1, 4, 7};
quickSort(initial, 0, initial.length - 1);
System.out.println(Arrays.toString(initial));
}
/**
* 快速排序算法：
* 取第一个数做中轴值，形成一个"坑"，定义左右两个索引，左边的索引从第二个数开始，右边的索引从最右边开始
* 先从右边的索引开始寻找，找到比中轴值小的数，则放到坑中，这个数所在的地方，则变成一个新的"坑"
* 再从左边开始寻找，找到比中轴值大的数，则放到新的坑中
* 当左边的索引=右边的索引时，将中轴值填入到当前的坑中，结束本次排序。
* 然后将中轴值的两遍的数，按照相同的方法，分别进行快排，直到中轴值左边的索引大于等于右边的索引
*/
//把left和right放到参数里，是因为每次递归排序，要传入左右的索引，每次递归都是变化的
public static void quickSort(int[] initial, int left, int right) {
//当达到结束的条件，结束递归
if (left >= right){
return;
}
int leftIndex = left;
int rightIndex = right;
//取第一个数做中轴值
int center = initial;
//只要左边的索引比右边的索引小，就要一直执行下去，直到两个索引重合,则代表当前的排序结束
while (leftIndex < rightIndex) {
//一直循环，直到找到比中轴值小的数
while (initial > center && leftIndex < rightIndex) {
rightIndex--;
}
//将比中轴值小的数放入到坑中,右边的索引所在的位置，则代表新的坑
initial = initial;
while (initial < center && leftIndex < rightIndex) {
leftIndex++;
}
initial = initial;
}
//此时initial=initial把中轴值填入坑中，本次排序结束
initial = center;
//递归，把左边进行快排
quickSort(initial, left, rightIndex - 1);
//递归，把右边进行快排
quickSort(initial, rightIndex + 1, right);
}
}
``` majia4075669072 发表于 2021-3-23 09:51
我记得快排有一个变种版的，可以固定住一端不动，去追另一端，这个版本的弄起来好一点。
你写的这种两边 ...
我只看到两个，一个尚硅谷的交换法，找到左右两边符合条件的，然后两个数做交换，我感觉那样子的不是很好，就直接看挖坑法，取第一个数做中轴数的 zjytrhy 发表于 2021-3-23 09:14
排序算法会递归就很好理解了，归并算法也是
递归倒是理解了，卡死在两个参数的传递转换了，一直没弄懂两个索引的变更是怎么实现的，看了好久 谢谢楼主的经验 感谢分享经验 这个看了N遍，好像也看懂了，就是记不住，因为实践中一次也没用到过 谢谢分享 感谢楼主分享，解决了我的疑惑。 排序算法会递归就很好理解了，归并算法也是 感谢分享！ 感谢楼主分享！ 我记得快排有一个变种版的，可以固定住一端不动，去追另一端，这个版本的弄起来好一点。
你写的这种两边往中间缩的，确实有点复杂，要考虑的corner case太多了。
页:
[1]
2