关于快速排序

2020 年 10 月 9 日算法

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

Haskell 实现

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

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

---

[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]