双边循环法(指针交换法)

    public static int[] quickSort(int[] array, int left, int right) {
        //递归出口条件
        if(left>right) return array;
        int temLeft = left, temRight = right, pivot = array[left];
        while (temLeft < temRight) {
            //从右边开始寻比标准值小的
            while (array[temRight] >= pivot && temLeft < temRight) {
                temRight--;
            }
            //从左边开始寻找比标准值大的
            while (array[temLeft] <= pivot && temLeft < temRight) {
                temLeft++;
            }
            //交换
            int tem = array[temLeft];
            array[temLeft] = array[temRight];
            array[temRight] = tem;
        }
        //归位基准值
        int tem = array[temLeft];
        array[temLeft] = array[left];
        array[left] = tem;
        //递归重复调用
        quickSort(array, temLeft + 1, right);
        quickSort(array, left, temRight - 1);
        
        return array;

单边循环法(填坑法)

public static void quickSort2(int[] a, int left, int right) {
    if (left >= right) return;
    int pivot = a[left], mark = left;
    for (int i = left+1; i <= right; i++) {
        //寻找小于基准值的,与mark下一个交换
        if (a[i] < pivot) {
            mark++;
            int tem = a[mark];
            a[mark] = a[i];
            a[i] = tem;
        }
    }
    //将pivot和mark所在位置交换
    a[left] = a[mark];
    a[mark] = pivot;
    quickSort2(a, mark+1, right);
    quickSort2(a, left, mark-1);
}
最后修改:2021 年 02 月 16 日
如果觉得我的文章对你有用,请随意赞赏