快速排序法

public static int adjustArray(int[] a, int first, int last){
        int i = first;
        int j = last;
        //取第一个数为基准数，也就是第一个坑
        int x = a[i];
        while (i < j){
            //从右向左找小于x的数来填坑
            //a[j]等于x或比x大则继续往左找
            while (i < j && a[j] >= x){
                j--;
            }
            //当找到a[j]比x小的数时，要先判断此时i是否小于j
            //然后把a[j]填入a[i]中，此时a[j]成为新的坑
            if (i < j){
                a[i] = a[j];
                i++;
            }
            //接着从左往右找大于等于x的数来填坑
            //a[i]比x小则继续往右找
            while (i < j && a[i] < x){
                i++;
            }
            //当找到a[i]大于等于x的数时，要先判断此时i是否小于j
            //然后把a[i]填入a[j]中，此时a[i]成为新的坑
            //然后这整个过程一直持续到i = j的时候退出
            if (i < j){
                a[j] = a[i];
                j--;
            }
        }
        //退出时，i = j，最后将x填到这个坑中
        a[i] = x;
        //返回的这个数为基准数最后落到的坑的位置，此时，基准数前面的数都比它小，后面的数都比他大
        //接下来要做的事情，是对基准数左边的部分和右边的部分重复这个方法
        return i;
    }
    
    public static void quick_sort1(int[] a, int first, int last){
        //刚开始肯定first比last小的，毕竟fisrt是0，last是a.length - 1;
        if (first < last){
            int i = adjustArray(a, first, last);
            //然后不断递归对i位置左边的那部分和i位置右边那部分调用此方法
            //直到调用不了为止，就排好序了
            quick_sort1(a, first, i - 1);
            quick_sort1(a, i + 1, last);
        }
    }
    
    //将以上两个方法合起来就是：
    public static void quick_sort(int[] a, int first, int last){
        if (first < last){
            int i = first;
            int j = last;
            int x = a[i];
            while (i < j){
                while (i < j && a[j] >= x){
                    j--;
                }
                if (i < j){
                    a[i] = a[j];
                    i++;
                }
                while (i < j && a[i] < x){
                    i++;
                }
                if (i < j){
                    a[j] = a[i];
                    j--;
                }
            }
            a[i] = x;
            quick_sort1(a, first, i - 1);
            quick_sort1(a, i + 1, last);
        }
    }

Written on October 16th, 2019