Fork me on GitHub

Swift-快速排序、双路快排和三路快排

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

快速排序

快速排序由 C. A. R. Hoare 在 1962 年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

下面我们来了解一下快排的子过程的思路：

快速排序是把数组中的一个元素挪到它排好序时应该所处的位置，如图：

首先选择数组中的一个元素，比如用 l 索引指向最左边的元素 v，逐渐遍历数组所有位于 l 左边的元素，在遍历的过程中，我们将逐渐整理出小于 v 的元素和大于 v 的元素，当然我们继续用一个索引 j 来记录小于 v 和大于 v 的分界点，然后我们当前访问的元素索引为 i。

那么 i 怎么处理呢？很简单当 i 指向的元素 e 大于 v 的时候，直接包含进大于 v 的部分中，像这样：

然后我们继续讨论下一个元素，此时 i++，如图：

如果元素 e 小于 v 的时候怎么做呢？只需要把元素 e 和橙色部分之后的一个元素交换，就可以了，此时索引 j++。如图：

最后i继续往后走，到最后的时候就直接将数组分成了等于 v，小于 v，大于 v 的三部分。

最后将 l 位置和 j 位置交换，就实现了快速排序的子过程，如图：

下面是快速排序代码（为 Array 添加扩展，只要数组中的元素支持 Comparable 协议，就可以用排序）：

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
extension Array where Element: Comparable {
    // MARK: - 快速排序
    @discardableResult mutating func quickSort() -> [Element] {
        
        __quickSort(l: 0, r: self.count - 1)
        
        return self
    }
    
    private mutating func __quickSort(l: Int, r: Int) -> Void {
        
        if l >= r {
            return;
        }
        
        let q = __quick(l: l, r: r)
        
        __quickSort(l: l, r: q - 1)
        __quickSort(l: q + 1, r: r)
    }
    
    private mutating func __quick(l: Int, r: Int) -> Int {
        
        let e = self[l]
        var j = l
        for i in l...r {
            if (self[i] < e) {
                swapAt(i, j + 1)
                j += 1
            }
        }
        swapAt(l, j)
        
        return j
    }
}

大家知道，快速排序虽然高效，但并不稳定，当数组中存在大量重复元素时，比如举个例子，我用模板测试归并排序和快速排序的时间，设置一个 100000 的数组，数组元素在 0-10 之间随机取值，那么用归并需要花费 1.33s 而快排需要花费 40.58s。当快速排序最优的时候是 O(n log n)，而此时显然退化到了 O(n^2) 的级别。这是为什么？

还记得上面写的快排的子过程么，考虑到了 e>v, e<v，而 e=v 的情况没有考虑。看了代码理解了的同学应该清楚，其实我是把等于 v 这种情况包含进了大于 v 的情况里面了，那么会出现什么问题？不管是当条件是大于等于还是小于等于 v，当数组中重复元素非常多的时候，等于 v 的元素太多，那么就将数组分成了极度不平衡的两个部分，因为等于 v 的部分总是集中在数组的某一边。

那么一种优化的方式便是进行 双路快排。

双路快排

和快排不同的是此时我们将小于 v 和大于 v 的元素放在数组的两端，那么我们将引用新的索引 j 的记录大于 v 的边界位置。如图：

i 索引不断向后扫描，当 i 的元素小于 v 的时候继续向后扫描，直到碰到了某个元素大于等于 v。j 同理，直到碰到某个元素小于等于 v。如图：

然后绿色的部分便归并到了一起，而此时只要交换 i 和 j 的位置就可以了，然后 i++，j– 就行了。如图：

直到 i 和 j 遍历完毕，整个数组排序完成。

这种优化当它遇到重复元素的时候，也能近乎将他们平分开来。

双路快排代码如下：

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
extension Array where Element: Comparable {
    // MARK: - 快速排序，双路快排
    @discardableResult mutating func quickSort2Way() -> [Element] {
        
        __quickSort2Way(l: 0, r: self.count - 1)
        
        return self
    }
    
    private mutating func __quickSort2Way(l: Int, r: Int) -> Void {
        
        if l >= r {
            return
        }
        
        let q = __quick2Way(l: l, r: r)
        
        __quickSort2Way(l: l, r: q - 1)
        __quickSort2Way(l: q + 1, r: r)
    }
    
    private mutating func __quick2Way(l: Int, r: Int) -> Int {
        
        let e = self[l]
        var j = l+1
        var k = r
        
        while true {
            
            while j <= r && self[j] <= e {
                j += 1
            }
            while k > l && self[k] > e {
                k -= 1
            }
            if j >= k {
                break
            }
            
            swapAt(j, k)
            
            j += 1
            k -= 1
        }
        
        swapAt(l, k)
        
        return k
    }
}

当然除了快排和双路快排，还有一个更加经典的优化，我们叫它 三路快排。

三路快排

双路快排将整个数组分成了小于 v，大于 v 的两部分，而三路快排则是将数组分成了小于 v，等于 v，大于 v 的三个部分，当递归处理的时候，遇到等于 v 的元素直接不用管，只需要处理小于 v，大于 v 的元素就好了。某一时刻的中间过程如下图：

当元素 e 等于 v 的时候直接纳入绿色区域之内，然后 i++ 处理下一个元素。如图：

当元素 e 小于 v 的时候，只需要将元素 e 与等于 e 的第一个元素交换就行了，这和刚开始讲的快速排序方法类似。同理，当大于 v 的时候执行相似的操作。如图：

当全部元素处理完之后，数组便成了这个样子：

三路快排的代码如下：

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
extension Array where Element: Comparable {
    // MARK: - 快速排序，三路快排
    @discardableResult mutating func quickSort3Way() -> [Element] {
        
        __quickSort3Way(l: 0, r: self.count - 1)
        
        return self
    }
    
    private mutating func __quickSort3Way(l: Int, r: Int) -> Void {
        
        if l >= r {
            return
        }
        
        let (lt, gt) = __quick3Way(l: l, r: r)
        
        __quickSort3Way(l: l, r: lt - 1)
        __quickSort3Way(l: gt + 1, r: r)
    }
    
    private mutating func __quick3Way(l: Int, r: Int) -> (Int, Int) {
        
        let e = self[l]
        var lt = l
        var i = l + 1
        var gt = r
        
        while i <= gt {
            while gt > l && self[gt] > e {
                gt -= 1
            }
            if i > gt {
                break
            }
            if self[i] < e {
                swapAt(i, lt + 1)
                lt += 1
                i += 1
            } else if self[i] > e {
                swapAt(i, gt)
                gt -= 1
            } else {
                i += 1
            }
        }
        swapAt(l, lt)
        
        return (lt, gt)
    }
}

写在最后

对比了一下这三个算法，在普通情况下，双路快排的速度已改算是最快的。（不同的环境下略有差异，数组内相等元素特别多的时候，三路快排性能更好）

1
2
3
4
// 数组中10万个元素，元素取值范围：0~10000
快速排序 排序完毕，耗时：0.8741459846496582
双路快排 排序完毕，耗时：0.4336860179901123
三路快排 排序完毕，耗时：0.7008020877838135

下面是随机产生 100万个 0~10000 的整数存放在数组中，来查看不同排序算法间的性能差异。

1
2
3
4
5
归并算法 排序完毕，耗时：12.888783931732178
快速排序 排序完毕，耗时：10.126990795135498
双路快排 排序完毕，耗时：7.646800994873047
三路快排 排序完毕，耗时：7.585190773010254
Swift 自带排序 排序完毕，耗时：1.39898681640625

相对于归并算法来说，双路快排已经很快了，但是对比 Swift 自带的 sort() 方法，发现它比我自己写的快排还要快好多，心里顿时很受打击，看来算法优化确实值得深钻研究啊。

The End ！

------------- 本文结束感谢您的阅读 -------------