快排序算法

发表于 分类于
学习笔记

示例

1
[2,1,6,5]    ===>   [1,2,5,6]

算法

随机设定一个支点, 把无序数组分为三个范围的数组, 分别是大于, 等于, 小于的数组;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public List<Integer> quicksort(List<Integer> nums) {
    if (nums.size() <= 1) return nums;
    int index = new Random().nextInt(nums.size());
    int pivot = nums.get(index);
    List<Integer> eq = new ArrayList<>();
    List<Integer> bigger = new ArrayList<>();
    List<Integer> smaller = new ArrayList<>();
    for (Integer i : nums) {
        if (i == pivot) {
            eq.add(i);
        } else if (i > pivot) {
            bigger.add(i);
        } else {
            smaller.add(i);
        }
    }
    List<Integer> newList = new ArrayList<>();
    newList.addAll(quicksort(smaller));
    newList.addAll(eq);
    newList.addAll(quicksort(bigger));
    return newList;
}

时间复杂度 O(n*log n)