关于快速排序

发表于 更新于

今天见到了好多种快速排序···感觉和我想象中的都不一样。

Haskell 实现

先放一种快排的 Haskell 实现，简单易懂：

1
2
3
4
5
6
qsort :: Int[] -> Int[]
qsort [] = []
qsort (x:xs) = qsort left ++ [x] ++ qsort right
  where
    left = [y | y<=xs, y < x]
    right = [y | y<=xs, y >= x]

核心思想

我认为快速排序的核心思想是分而治之，将数组头去除后的部分以数组头为界进行分类，然后将分类后的小数组再次去头然后分类处理，以此循环，直到数组长度为 1 。

逻辑顺序

  1. 取数组首元素 key
  2. 从第二个元素开始遍历数组
  3. 比 key 小的元素放进数组 left
  4. 比 key 大的元素放进数组 right
  5. 将 left 与 right 各自排序（递归）
  6. 连接 left + key + right
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
[9, 0, 3, 2, 6, 7, 6]
 ^

[0, 3, 2, 6, 7, 6] 9 []
 ^

[0 [3, 2, 6, 7, 6]] 9 []
    ^

[0 [[2] 3 [6, 7, 6]]] 9 []
           ^

[0 [[2] 3 [6 [7, 6]]]] 9 []
              ^

[0 [[2] 3 [6 [[6] 7]]]] 9 []

[0, 2, 3, 6, 6, 7, 9]