本帖最后由 逸帅 于 2021-3-23 00:05 编辑
1、项目场景：
记录一次快速排序遇坑史，周围的室友、朋友不会数据结构和算法...
无奈，今天大部分时间都在快速排序上面了
2、问题描述：
1.快速排序传值的左边索引和右边索引一直是变化的，没理解怎么变化的
2.使用了递归，递归没有加return
3、原因分析：
- 每次递归的左边索引和右边索引都是变化的，每次排序后，中轴值的索引，是左边元素的最右边索引，是右边元素最左边的索引，但是左边元素的左边索引，还是上次排序的左边索引，右边元素的右边索引，还是上次排序的右边索引。
也就是说，下一次还要用到上一次的左边索引和右边索引，所以要保留这两个索引
例如：
第一次:左边索引是0，右边索引是length-1，中轴值假设是center，排序后，中轴值左边的元素数组称为左数组，右边的元素数组称为右数组
第二次:左数组的左边索引还是0，但是右边索引是center-1，右数组的右边索引是length-1，左边索引是center+1
以此类推，所以左边的索引和右边的索引，每次都需要传值进去，因为一直在变化。
4、解决方案：
1、将左边的索引和右边的索引分别赋值给一个新的变量
public static void quickSort(int[] initial, int left, int right) {
int leftIndex = left;
int rightIndex = right;
//取第一个数做中轴值
int center = initial[leftIndex];
2、添加结束递归的条件
public static void quickSort(int[] initial, int left, int right) {
//当达到结束的条件，结束递归
if (left >= right){
return;
}
5、完整的代码：
package com.yishuai.sort;
import java.util.Arrays;
/**
* home.php?mod=space&uid=686208 yishuai
* @description 快速排序算法
* home.php?mod=space&uid=686237 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[leftIndex];
//只要左边的索引比右边的索引小，就要一直执行下去，直到两个索引重合,则代表当前的排序结束
while (leftIndex < rightIndex) {
//一直循环，直到找到比中轴值小的数
while (initial[rightIndex] > center && leftIndex < rightIndex) {
rightIndex--;
}
//将比中轴值小的数放入到坑中,右边的索引所在的位置，则代表新的坑
initial[leftIndex] = initial[rightIndex];
while (initial[leftIndex] < center && leftIndex < rightIndex) {
leftIndex++;
}
initial[rightIndex] = initial[leftIndex];
}
//此时initial[left]=initial[right]把中轴值填入坑中，本次排序结束
initial[rightIndex] = center;
//递归，把左边进行快排
quickSort(initial, left, rightIndex - 1);
//递归，把右边进行快排
quickSort(initial, rightIndex + 1, right);
}
}
| 
发表于 2021-3-23 00:02
|
发表于 2021-3-23 10:00
