Java数据结构与算法Day18--快速排序

看起来很简单的一个逻辑

假设我取中间的数为基数,如下图

 结合代码来看,我们第一次调用quickSort的流程如下

然后对两侧进行递归调用,看起来确实简单,但是中间关于L、R的指向有很多特殊的情况,如果不着重判断,会导致死循环

import java.util.Arrays;
import java.util.Random;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = new int[]{1,5,4,2,3};
        quickSort(arr,0,arr.length - 1);
        System.out.println(Arrays.toString(arr));
//        int[] arr1 = new int[80000];
//        Random random = new Random();
//        for (int i = 0; i < arr1.length; i++) {
//            arr1[i] = random.nextInt(80000);
//        }
//        long start = System.currentTimeMillis();
//        quickSort(arr1,0, arr1.length - 1);
//        long end = System.currentTimeMillis();
//        System.out.println("用时:"+(end - start));
    }
    public static void quickSort(int[] arr,int left_index,int right_index){
        int l = left_index;
        int r = right_index;
        //mid为基数
        int mid = arr[(l + r) / 2];
        //用来交换的变量
        int tmp;
        while (l < r){
            //跳出循环时arr[l] >= mid
            //也就是在左半边找到了一个可以被放到右边的数
            while (arr[l] < mid)
                l++;
            //跳出循环时arr[r] <= mid
            //也就是在右半边找到了一个可以被放到左边的数
            while (arr[r] > mid)
                r--;
            //如果发现l >= r,证明左边没有小于基数的数,右边没有大于基数的数
            if (l >= r)
                //退出条件
                break;
            else{
                //如果不是l >= r,就证明是需要交换位置(大的放右边,小的放左边)
                tmp = arr[r];
                arr[r] = arr[l];
                arr[l] = tmp;
            }
            //下面的两个if对应图2
            if (arr[l] == mid)
                r--;
            if (arr[r] == mid)
                l++;
        }
        //如果不把l.r错开,会导致右半部遍历无法跳出,而且必须l ++
        //因为我们使用的是整数除,在还有两个数的时候
        //如果不错位,l永远是等于0(指向左边那个数),永远小于right_index(1)
        if (l == r){
            l ++;
        }
        //进行左半部遍历
        if (left_index < r){
            quickSort(arr,left_index,r);
        }
        //进行右半部遍历
        if (right_index > l){
            quickSort(arr,l,right_index);
        }
    }
}

上图为图②,对应代码注释中的一个逻辑判断,如果不进行一个判断,会永远循环