数组快速排序的代码理解

Question

package com.itheima.myquitesort;

/**

• 快速排序算法代码实现

• ---- 难度较大，若不能理解，想象生活中按大小个战队

• /
  public class MyQuiteSortDemo2 {
  public static void main(String[] args) {

    /*
        1.从右开始找比基准数小的
        2.从左开始找比基准数大的
        3.交换两个值的位置
        4.红色继续往左找，蓝色继续往右找，直到两个箭头指向同一个索引为止
        5.基准数归位
     */
    int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
  
    quiteSort(arr, 0, arr.length - 1);//后面的两个参数表示要排序的范围【最小的索引，最大的索引】
  
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + " ");
    }
  

  }

  private static void quiteSort(int[] arr, int left, int right) {

    //递归的停止条件
    if (right < left) {
        return;
    }
    /*
        临时存储的原因：
        1.left和right要不断地变化
        2.基准数归位时要使用到最原始的left和right
     */
    int left0 = left;
    int right0 = right;
  
    //计算出基准数
    int baseNumber = arr[left0];
  
    while (left != right) {
        //1.从右开始找比基准数小的
        while (arr[right] >= baseNumber && right > left) {
            right--;
        }
        //2.从左开始找比基准数大的
        while (arr[left] <= baseNumber && right > left) {
            left++;
        }
        //3.交换两个值的位置
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
    //4.基准数归位
    int temp = arr[left];
    arr[left] = arr[left0];
    arr[left0] = temp;
  
    quiteSort(arr, 0, left - 1);
    quiteSort(arr, left + 1, right0);
  

  }
  }
  最后两行代码中，为啥不是left0-1，left0+1，即基准值索引应该是left0还是left？而且第二次递归的时候不应该是右半边，从基准值索引+1到最大索引值吗，那最大索引值不应该就是原数组arr的长度-1，即arr.length-1吗？但是替换成我说的这些，就会运行报出栈内存溢出错误异常

Answer 1

这时候你就要理清楚有0的才是边界值还是没0的。在你的快速排序方法中，第10跟11行的left0跟right0就是边界值。你应该这么想，左右指针在这两个边界点分别相向移动，遇到能交换的情况就交换，直到左右指针相遇。此时左右指针所指值相等，将该值与基准点交换，那么基准点就在两指针重合位置，这个位置是left而不是left0.重复上面方法在对该位置左右区间再进行排序。我博客里边有个快排思路，跟你这个差不多，感兴趣可以了解一下