Java 单边快排 与 双边快排

目录

一、单边快排

二、双边快排

一、单边快排

代码：已是该算法的最优情况

package com.wxl;

import java.lang.reflect.Array;
import java.util.Arrays;

public class Test {

    public static void main(String[] args) {
        int[] arr = {5, 3, 7, 2, 9, 8, 1, 4};
        singleFastSort(arr);
    }


    private static void swap(int[] arr, int pre, int after) {
        if (arr[pre] > arr[after]) {
            int temp = arr[pre];
            arr[pre] = arr[after];
            arr[after] = temp;
        }
    }

    private static void singleFastSort(int[] arr) {
        singleFastSortRecursion(arr, 0, arr.length - 1);
        System.out.println("最终结果：");
        System.out.println(Arrays.toString(arr));
    }

    private static void singleFastSortRecursion(int[] arr, int startIndex, int endIndex) {
        if (startIndex >= endIndex) {
            return;
        }
        int p = singleFastSortPartition(arr, startIndex, endIndex);
        singleFastSortRecursion(arr, startIndex, p - 1);//左边区域继续调用
        singleFastSortRecursion(arr, p + 1, endIndex);//右边区域继续调用
    }

    private static int singleFastSortPartition(int[] arr, int startIndex, int endIndex) {
        int i = startIndex;//最小下标标记指针
        int standpoint = arr[endIndex];//基准点，取最右边
        for (int j = startIndex; j < endIndex; j++) {
            if (arr[j] < standpoint) {
                if (i != j) {
                    swap(arr, i, j);
                }
                i++;//后移一位
            }
        }
        if (i != endIndex) {
            swap(arr, i, endIndex);
        }
        System.out.println(Arrays.toString(arr) + " i=" + i);

        return i;//返回边界下标
    }
}

运行结果：

[3, 2, 1, 4, 9, 8, 7, 5] i=3
[1, 2, 3, 4, 9, 8, 7, 5] i=0
[1, 2, 3, 4, 9, 8, 7, 5] i=2
[1, 2, 3, 4, 5, 8, 7, 9] i=4
[1, 2, 3, 4, 5, 8, 7, 9] i=7
[1, 2, 3, 4, 5, 7, 8, 9] i=5
最终结果：
[1, 2, 3, 4, 5, 7, 8, 9]

单边快排排序逻辑：

数组：5, 3, 7, 2, 9, 8, 1, [4]
基准点用[]，拍好序的部分用()，下次排序的部分{}
第一次排序：{3, 2, [1]}, (4), 9, 8, 7, 5          i=3
第二次排序：(1), {2, [3]}, (4), 9, 8, 7, 5        i=0
第三次排序：(1, 2, 3, 4), {9, 8, 7, [5]}          i=1
第四次排序：(1, 2, 3, 4, 5), {8, 7, [9]}          i=4
第五次排序：(1, 2, 3, 4, 5), {8, [7]}, (9)        i=7
第六次排序：(1, 2, 3, 4, 5, 7, 8, 9)              i=5

二、双边快排

代码：

package com.wxl;

import java.util.Arrays;

public class Test {

    public static void main(String[] args) {
        int[] arr = {5, 3, 7, 2, 9, 8, 1, 4};
        dubbleFastSort(arr);
    }


    private static void swap(int[] arr, int pre, int after) {
        if (arr[pre] > arr[after]) {
            int temp = arr[pre];
            arr[pre] = arr[after];
            arr[after] = temp;
        }
    }

    private static void dubbleFastSort(int[] arr) {
        dubbleFastSortRecursion(arr, 0, arr.length - 1);
        System.out.println("最终结果：");
        System.out.println(Arrays.toString(arr));
    }

    private static void dubbleFastSortRecursion(int[] arr, int startIndex, int endIndex) {
        if (startIndex >= endIndex) {
            return;
        }
        int p = dubbleFastSortPartition(arr, startIndex, endIndex);
        dubbleFastSortRecursion(arr, startIndex, p - 1);//左边区域继续调用
        dubbleFastSortRecursion(arr, p + 1, endIndex);//右边区域继续调用
    }

    private static int dubbleFastSortPartition(int[] arr, int startIndex, int endIndex) {
        int standPoint = arr[startIndex];//基准点
        int i = startIndex;//从左往右找大于基准点
        int j = endIndex;//从右往左找小于基准点
        while (i < j) {
            while (i < j && arr[j] > standPoint) {
                j--;
            }
            while (i < j && arr[i] <= standPoint) {
                i++;
            }
            swap(arr, i, j);
        }
        swap(arr, startIndex, j);
        System.out.println(Arrays.toString(arr) + " j=" + j);
        return j;
    }
}

运行结果：

[1, 3, 4, 2, 5, 8, 9, 7] j=4
[1, 3, 4, 2, 5, 8, 9, 7] j=0
[1, 2, 3, 4, 5, 8, 9, 7] j=2
[1, 2, 3, 4, 5, 7, 8, 9] j=6
最终结果：
[1, 2, 3, 4, 5, 7, 8, 9]

双边快排排序逻辑：

数组：[5], 3, 7, 2, 9, 8, 1, 4
基准点用[]，拍好序的部分用()，下次排序的部分{}
第一次排序：{[1], 3, 4, 2}, (5), 8, 9, 7            j=4
第二次排序：(1), {[3], 4, 2}, (5), 8, 9, 7          j=0
第三次排序：(1), 2, (3), 4, (5), {[8], 9, 7}        j=2
第四次排序：(1, 2, 3, 4, 5), 7, (8), 9              j=6

可以看到双边快排比单边快排效率高些