Java深入浅出理解快速排序以及优化方式

public void swap(int[] array, int L, int R) {
    int tmp = array[L];
    array[L] = array[R];
    array[R] = tmp;
}

//挖坑法-升序
public int partition(int[] array, int L, int R) {
    int tmp = array[L]; //保存基准值
    while (L < R) {
        //先从右边找一个数
        while (L < R && array[R] >= tmp) {
            R--; //找小于基准值的数
        }
        array[L] = array[R];
        
        //再从左边找一个数
        while (L < R && array[L] <= tmp) {
            L++; //找大于基准值的数
        }
        array[R] = array[L];
    }
    array[L] = tmp; //将基准值放入中间位置
    return L; //返回此时基准值的下标，用于将数组分为两部分
}

public void quick(int[] array, int L, int R) {
    if (L >= R) {
        return;
    }
    int p = partition(array, L, R); //返回基准值的下标
    quick(array, L, p - 1); //递归左半部分
    quick(array, p + 1, R); //递归右半部分
}

public void quick2(int[] array, int L, int R) {
    if (L >= R) {
        return;
    }
    int index = L + (int)((R - L) * Math.random()); //生成L~R之间的随机值
     //为了好理解，我将这个随机值放到数组开头。也可以不交换，只需改partition即可
    swap(array, L, index);
    
    int p = partition(array, L, R); //调用挖坑法
    quick2(array, L, p - 1); //递归左半部分
    quick2(array, p + 1, R); //递归右半部分
}

public void quick3(int[] array, int L, int R) {
    if (L >= R) {
        return;
    }
    threeNumberMid(array, L, R); //三数取中，并将中间值，放到数组最前面
    int p = partition(array, L, R);
    quick3(array, L, p - 1);
    quick3(array, p + 1, R);
}

private void threeNumberMid(int[] array, int L, int R) {
    int mid = L + ((R - L) >> 1); //中间值
    if (array[L] > array[R]) {
        swap(array, L, R);
    }
    if (array[L] > array[mid]) {
        swap(array, L, mid);
    }
    if (array[mid] > array[R]) {
        swap(array, mid, R);
    }
    //以上三个if过后，这三个数就是一个升序
    //然后将中间值，放到数组的最前面
    swap(array, L, mid);
}

//伪代码
public int[] partition(int[] array, int L, int R) {
    int less = L - 1;
    int more = R;
    int index = L;
    while (index < more) { //index和more相遇就停止
        if (array[index] > 基准值) {
            
        } else if (array[index] < 基准值) {
            
        } else { //等于基准值时，index后移即可
            index++;
        }
    }
    
    //返回等于区的开始和结束下标即可。
}

//R位置就是基准值
public int[] partition(int[] array, int L, int R) {
    if (L > R) {
        return new int[] {-1, -1};
    }
    if (L == R) {
        return new int[] {L, L};
    }
    
    int less = L - 1; //数组最前面开始为less
    int more = R; //数组末尾，包括了最后的基准值
    int index = L; //遍历数组
    while (index < more) {
        if(array[index] > array[R]) { //大于区
            swap(array, index, --more);
        } else if (array[index] < array[R]) { //小于区
            swap(array, index++, ++less);
        } else { //等于区
            index++;
        }
    }
    swap(array, more, R); //将最后的基准值放回等于区
    //此时的范围：L …… less 是小于区。less+1 ……more 是等于区。more + 1 …… R是大于区
    return new int[] {less+1, more};
}

public void quick(int[] array, int L, int R) {
    if (L >= R) {
        return;
    }
    int i = L + (int)((R - L) * Math.random()); //随机值
    swap(array, i, R); //放到数组的最后
    int[] mid = partition(array, L, R); //返回的是等于区的范围
    quick(array, L, mid[0] - 1); //左半部分
    quick(array, mid[0] + 1, R); //右半部分
}

//非递归版本
public void quick(int[] array) {
    Stack<Integer> stack = new Stack<>();
    stack.push(0);
    stack.push(array.length - 1); 
    
    while (!stack.isEmpty()) {
        int R = stack.pop();
        int L = stack.pop();
        int[] mid = partition(array, L, R); //调用荷兰国旗问题优化的代码
        
        if (mid[1] + 1 < R) {
            stack.push(mid[1] + 1);
            stack.push(R);
        }
        if (mid[0] - 1 > L) {
            stack.push(L);
            stack.push(mid[0] - 1);
        }
    }
}