Java快速排序算法

来一个Java版本的快速排序。

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {5, 2, 4, 7, 1, 8, 3, 4};
        printArray(arr);
        quickSort(arr, 0, arr.length - 1);
        printArray(arr);
    }

    static void quickSort(int[] arr, int i, int j) {
        if (i < j) {
            int pos = partition(arr, i, j);
            printArray(arr);
            System.out.println("分别排左边和右边");
            quickSort(arr, 0, pos - 1);
            quickSort(arr, pos + 1, j);
        }
    }

    static int partition(int[] arr, int i, int j) {
        int pivot = arr[j];
        System.out.println("基准值：" + pivot);
        int cursor = i;
        System.out.println("游标：" + cursor);

        for (int k = i; k < j; k++) {
            System.out.println("循环到第[" + k + "]个值");
            if (arr[k] <= pivot) {
                System.out.println("交换位置[" + cursor + "]与[" + k + "]的值");
                swap(arr, k, cursor);
                cursor += 1;
            }
            System.out.print("循环完成后：");
            printArray(arr);
            System.out.println("游标：" + cursor);
        }
        System.out.println("交换位置[" + cursor + "]与[" + j + "]的值");
        swap(arr, j, cursor);

        System.out.println("游标：" + cursor);

        return cursor;
    }

    static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    static void printArray(int[] arr) {
        StringBuilder sb = new StringBuilder();
        for (int anArr : arr) {
            sb.append(anArr).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
}

输出如下：

5 2 4 7 1 8 3 4
基准值：4
游标：0
循环到第[0]个值
循环完成后：5 2 4 7 1 8 3 4
游标：0
循环到第[1]个值
交换位置[0]与[1]的值
循环完成后：2 5 4 7 1 8 3 4
游标：1
循环到第[2]个值
交换位置[1]与[2]的值
循环完成后：2 4 5 7 1 8 3 4
游标：2
循环到第[3]个值
循环完成后：2 4 5 7 1 8 3 4
游标：2
循环到第[4]个值
交换位置[2]与[4]的值
循环完成后：2 4 1 7 5 8 3 4
游标：3
循环到第[5]个值
循环完成后：2 4 1 7 5 8 3 4
游标：3
循环到第[6]个值
交换位置[3]与[6]的值
循环完成后：2 4 1 3 5 8 7 4
游标：4
交换位置[4]与[7]的值
游标：4
2 4 1 3 4 8 7 5
分别排左边和右边
基准值：3
游标：0
循环到第[0]个值
交换位置[0]与[0]的值
循环完成后：2 4 1 3 4 8 7 5
游标：1
循环到第[1]个值
循环完成后：2 4 1 3 4 8 7 5
游标：1
循环到第[2]个值
交换位置[1]与[2]的值
循环完成后：2 1 4 3 4 8 7 5
游标：2
交换位置[2]与[3]的值
游标：2
2 1 3 4 4 8 7 5
分别排左边和右边
基准值：1
游标：0
循环到第[0]个值
循环完成后：2 1 3 4 4 8 7 5
游标：0
交换位置[0]与[1]的值
游标：0
1 2 3 4 4 8 7 5
分别排左边和右边
基准值：5
游标：5
循环到第[5]个值
循环完成后：1 2 3 4 4 8 7 5
游标：5
循环到第[6]个值
循环完成后：1 2 3 4 4 8 7 5
游标：5
交换位置[5]与[7]的值
游标：5
1 2 3 4 4 5 7 8
分别排左边和右边
基准值：4
游标：0
循环到第[0]个值
交换位置[0]与[0]的值
循环完成后：1 2 3 4 4 5 7 8
游标：1
循环到第[1]个值
交换位置[1]与[1]的值
循环完成后：1 2 3 4 4 5 7 8
游标：2
循环到第[2]个值
交换位置[2]与[2]的值
循环完成后：1 2 3 4 4 5 7 8
游标：3
循环到第[3]个值
交换位置[3]与[3]的值
循环完成后：1 2 3 4 4 5 7 8
游标：4
交换位置[4]与[4]的值
游标：4
1 2 3 4 4 5 7 8
分别排左边和右边
基准值：4
游标：0
循环到第[0]个值
交换位置[0]与[0]的值
循环完成后：1 2 3 4 4 5 7 8
游标：1
循环到第[1]个值
交换位置[1]与[1]的值
循环完成后：1 2 3 4 4 5 7 8
游标：2
循环到第[2]个值
交换位置[2]与[2]的值
循环完成后：1 2 3 4 4 5 7 8
游标：3
交换位置[3]与[3]的值
游标：3
1 2 3 4 4 5 7 8
分别排左边和右边
基准值：3
游标：0
循环到第[0]个值
交换位置[0]与[0]的值
循环完成后：1 2 3 4 4 5 7 8
游标：1
循环到第[1]个值
交换位置[1]与[1]的值
循环完成后：1 2 3 4 4 5 7 8
游标：2
交换位置[2]与[2]的值
游标：2
1 2 3 4 4 5 7 8
分别排左边和右边
基准值：2
游标：0
循环到第[0]个值
交换位置[0]与[0]的值
循环完成后：1 2 3 4 4 5 7 8
游标：1
交换位置[1]与[1]的值
游标：1
1 2 3 4 4 5 7 8
分别排左边和右边
基准值：8
游标：6
循环到第[6]个值
交换位置[6]与[6]的值
循环完成后：1 2 3 4 4 5 7 8
游标：7
交换位置[7]与[7]的值
游标：7
1 2 3 4 4 5 7 8
分别排左边和右边
基准值：7
游标：0
循环到第[0]个值
交换位置[0]与[0]的值
循环完成后：1 2 3 4 4 5 7 8
游标：1
循环到第[1]个值
交换位置[1]与[1]的值
循环完成后：1 2 3 4 4 5 7 8
游标：2
循环到第[2]个值
交换位置[2]与[2]的值
循环完成后：1 2 3 4 4 5 7 8
游标：3
循环到第[3]个值
交换位置[3]与[3]的值
循环完成后：1 2 3 4 4 5 7 8
游标：4
循环到第[4]个值
交换位置[4]与[4]的值
循环完成后：1 2 3 4 4 5 7 8
游标：5
循环到第[5]个值
交换位置[5]与[5]的值
循环完成后：1 2 3 4 4 5 7 8
游标：6
交换位置[6]与[6]的值
游标：6
1 2 3 4 4 5 7 8
分别排左边和右边
基准值：5
游标：0
循环到第[0]个值
交换位置[0]与[0]的值
循环完成后：1 2 3 4 4 5 7 8
游标：1
循环到第[1]个值
交换位置[1]与[1]的值
循环完成后：1 2 3 4 4 5 7 8
游标：2
循环到第[2]个值
交换位置[2]与[2]的值
循环完成后：1 2 3 4 4 5 7 8
游标：3
循环到第[3]个值
交换位置[3]与[3]的值
循环完成后：1 2 3 4 4 5 7 8
游标：4
循环到第[4]个值
交换位置[4]与[4]的值
循环完成后：1 2 3 4 4 5 7 8
游标：5
交换位置[5]与[5]的值
游标：5
1 2 3 4 4 5 7 8
分别排左边和右边
基准值：4
游标：0
循环到第[0]个值
交换位置[0]与[0]的值
循环完成后：1 2 3 4 4 5 7 8
游标：1
循环到第[1]个值
交换位置[1]与[1]的值
循环完成后：1 2 3 4 4 5 7 8
游标：2
循环到第[2]个值
交换位置[2]与[2]的值
循环完成后：1 2 3 4 4 5 7 8
游标：3
循环到第[3]个值
交换位置[3]与[3]的值
循环完成后：1 2 3 4 4 5 7 8
游标：4
交换位置[4]与[4]的值
游标：4
1 2 3 4 4 5 7 8
分别排左边和右边
基准值：4
游标：0
循环到第[0]个值
交换位置[0]与[0]的值
循环完成后：1 2 3 4 4 5 7 8
游标：1
循环到第[1]个值
交换位置[1]与[1]的值
循环完成后：1 2 3 4 4 5 7 8
游标：2
循环到第[2]个值
交换位置[2]与[2]的值
循环完成后：1 2 3 4 4 5 7 8
游标：3
交换位置[3]与[3]的值
游标：3
1 2 3 4 4 5 7 8
分别排左边和右边
基准值：3
游标：0
循环到第[0]个值
交换位置[0]与[0]的值
循环完成后：1 2 3 4 4 5 7 8
游标：1
循环到第[1]个值
交换位置[1]与[1]的值
循环完成后：1 2 3 4 4 5 7 8
游标：2
交换位置[2]与[2]的值
游标：2
1 2 3 4 4 5 7 8
分别排左边和右边
基准值：2
游标：0
循环到第[0]个值
交换位置[0]与[0]的值
循环完成后：1 2 3 4 4 5 7 8
游标：1
交换位置[1]与[1]的值
游标：1
1 2 3 4 4 5 7 8
分别排左边和右边
1 2 3 4 4 5 7 8