QuickSort

发表于 更新于 分类于 ， 阅读次数： 本文字数： 520 阅读时长 ≈ 2 分钟

快速排序（Quicksort），又称分区交换排序（partition-exchange sort），简称快排，是一种高效的排序算法。由英国计算机科学家 Tony Hoare 于 1959 年开发并于 1961 年发表，至今它仍然是一种常用的排序算法。事实上，如果实施得当，它可以比归并排序、堆排序快两到三倍。

快速排序（Quicksort）

基本原理

快速排序是图灵奖得主 C. R. A. Hoare 于 1960 年提出的一种划分交换排序，它采用了一种分治的策略，通常称其为 分治法(Divide-and-ConquerMethod)。

分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地求解这些子问题，然后将这些子问题的解组合为原问题的解。

算法步骤

  1. 从序列中挑出一个元素，作为"基准" (pivot)
  2. 把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准值的后面（相同的数可以放到任一边），这个操作称为分区 (partition) 操作，分区操作结束后，基准元素所处的位置就是最终排序后它的位置
  3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序，直到所有子序列的大小为 0 或 1，这时整体已经排好序了

算法图解

传送门 坐在马桶上看算法：快速排序

动画演示

QuickSort

参考实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.util.Arrays;
import java.util.LinkedList;

/**
 * @author wylu
 */
public class QuickSort {
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static int partition(int[] arr, int left, int right) {
        int i = left, j = right, pivot = arr[left];
        while (i < j) {
            while (i < j && arr[j] >= pivot) j--;
            while (i < j && arr[i] <= pivot) i++;
            if (i < j) swap(arr, i, j);
        }
        arr[left] = arr[i];
        arr[i] = pivot;
        return i;
    }

    public static void recursiveSort(int[] arr, int left, int right) {
        if (left < right) {
            int idx = partition(arr, left, right);
            recursiveSort(arr, left, idx - 1);
            recursiveSort(arr, idx + 1, right);
        }
    }

    public static void nonRecursiveSort(int[] arr, int left, int right) {
        LinkedList<Integer> stack = new LinkedList<>();
        stack.push(left);
        stack.push(right);
        while (!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            if (left < right) {
                int idx = partition(arr, left, right);
                stack.push(left);
                stack.push(idx - 1);
                stack.push(idx + 1);
                stack.push(right);
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 9, 6, 0, 7, 2, 5, 8};
//        QuickSort.recursiveSort(arr, 0, arr.length - 1);
        QuickSort.nonRecursiveSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

partition的另一种写法，选取最右元素作为基准

1
2
3
4
5
6
7
8
public static int partition2(int[] arr, int left, int right) {
    int j = left - 1;
    for (int i = left; i < right; i++) {
        if (arr[i] <= arr[right]) swap(arr, i, ++j);
    }
    swap(arr, ++j, right);
    return j;
}

复杂度分析

排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 排序方式 稳定性
快速排序 \(O(nlogn)\) \(O(nlogn)\) \(O(n^2)\) \(O(logn) \sim O(n)\) In-place 不稳定

References

https://en.wikipedia.org/wiki/Quicksort

http://developer.51cto.com/art/201403/430986.htm

https://youliao.163yun.com/api-server/rss/xiaomi/item/IN2WDOMKAWVNTZV.html?ref=browser_news&s=mb&cp=cn-netease-youliao-browser&docid=44797c69e120935b2c4790d933d02a9b&itemtype=news&cateCode=rec&category=%E7%A7%91%E6%8A%80