huhu的小世界

1
package org.example;
2

3
import java.io.*;
4

5
public class Main {
6

7
    static int[] arr = {1 ,3, 2, 4, 1, 4, 6 ,2};
8

9
    public static void main(String[] args) {
10
        quickSort(0 ,arr.length - 1);
11
        ArrUtil.printArr(arr);
12
    }
13

14
    public static void quickSort (int l ,int r) {
15
        if (l >= r) {
16
            return;
17
        }
18
        //随机抽取一个数组值，才能在概率上把我快速排序的时间复杂度收敛到n * logn
19
        int x = arr[l + (int) (Math.random() * (r - l + 1))];
20
        partition (l ,r ,x);
21
        //为了防止底层的递归过程覆盖全局变量，用临时的变量记录first、last
22
        int left = first;
23
        int right = last;
24
        quickSort(l ,left - 1);
25
        quickSort(right + 1 ,r);
26
    }
27

28
    static int first;
29
    static int last;
30

31
    //已知数组在l到r的范围内一定有x这个值
32
    //划分数组，<x的放左边，==x的放中间，>x的放右边
33
    //把全局变量first，last更新为==x的左右边界
34
    private static void partition(int l, int r, int x) {
35
        first = l;
36
        last = r;
37
        int i = l;
38
        while (i <= last) {
39
            if (arr[i] == x) i ++;
40
            else if (arr[i] < x) swap(first ++ ,i ++);
41
            else swap(i ,last --);
42
        }
43
    }
44

45
    private static void swap(int a, int b) {
46
        int temp = arr[a];
47
        arr[a] = arr[b];
48
        arr[b] = temp;
49
    }
50
}