算法第4版(塞奇威克)学习——排序

作者: shen888 | 来源:发表于2019-11-27 17:56 被阅读0次

排序就是将一组对象按照某种逻辑顺序重新排列的过程，所有计算机系统都实现了各种排序算法以供系统和用户使用。学习排序算法有三大实际意义：

对排序算法的分析将有助于你全面理解比较算法性能的方法；
类似的技术也能有效解决其他类型的问题；
排序算法常常是我们解决其他问题的第一步。

本文中我们学习几种经典的排序算法，并高效的实现了“优先队列”这种基础数据类型。我们将讨论比较排序算法的理论基础并在结尾总结若干排序算法和优先队列的应用。

一、初级排序算法

我们先学习两种初级排序算法及其中一种的一个变体。深入学习这些相对简单算法的原因在于：

熟悉一些术语和简单技巧；
这些简单算法在某些情况下比之后学习的复杂算法更有效；
它们有助于我们改进复杂算法的效率。

1. 游戏规则

我们关注的主要对象是重新排列数组元素的算法（通常按照大小或者字母顺序）。从小到大排列
下面的 Sort 类展示了我们的习惯约定：我们使用子类来继承 Sort 来实现不同的排序实现，例如 Insertion、Merge、Quick 等。
例如输入：["S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"]
输出：["A", "E", "E", "L", "M", "O", "P", "R", "S", "T", "X"]

class Sort<Sortable> where Sortable: Comparable {
    init(args: [Sortable]) {
        var a = args
        sort(a: &a)
        assert(isSorted(a: a))
        show(a: a)
    }
    func sort(a: inout [Sortable]) {
        /* 请见算法1.1、算法1.2、算法1.3、算法1.4、算法1.5、算法1.7 */
    }
    func exch(a: inout [Sortable], i: Int, j: Int) {
        let t = a[I]
        a[i] = a[j]
        a[j] = t
    }
    func less(v: Sortable, w: Sortable) -> Bool {
        return v < w
    }
    private func show (a: [Sortable]) {
        print(a)
    }
    func isSorted(a: [Sortable]) -> Bool {
        // 测试数组元素是否有序
        for i in 1..<a.count {
            if less(v: a[i], w: a[i-1]) {
                return false
            }
        }
        return true
    }
}

验证：无论数组初始状态是什么，排序算法都能成功吗？谨慎起见使用 assert(isSorted(a: a)) 来确认排序的正确性。

运行时间：我们要评估算法性能。首先要计算各个排序算法在不同的随机输入下的基本操作的次数（包括比较和交换，或者是读写数组的次数）。然后我们用这些数据来估计算法的性能并介绍在实验中验证这些猜想所使用的工具。

排序成本模型。在研究排序算法时，我们需要计算比较和交换的数量。对于不交换元素的算法，我们会计算访问数组的次数

额外内存使用：排序算法的额外内存开销和运行时间同样重要。排序算法可以分为两类：除了函数调用所需的栈和固定数目的实例变量之外无须额外内存的原地排序算法，以及需要额外内存空间来存储另外一份数组副本的其他排序算法。

数据类型：我们的排序算法模板适用于任何实现了 Comparable 协议的数据类型。好处是系统实现了 Camparable 数组的排序方法，因此你可以直接用这些类型数组作为参数调用我们的排序方法。

2. 选择排序

一种最简单的排序算法是：找到数组中最小的那个元素，将它和数组的第一个元素交换位置，然后剩下的元素中找最小元素，与第二个元素交换位置。如此往复，直到排完整个数组，这种方法叫做选择排序。

算法1.1

class Selection<Sortable>: Sort<Sortable> where Sortable: Comparable {
    override func sort(a: inout [Sortable]) {
        let N = a.count
        for i in 0..<N {
            var min = I;
            for j in i..<N {
                if less(v:a[j], w:a[min]) {
                    min = j
                }
            }
            exch(a: &a, i: i, j: min);
        }
    }
}

算法1.1：选择排序的轨迹

如算法 1.1 所示，交换元素的代码写在内循环之外，每次交换都能排定一个元素，因此交换的总次数是 N。所以算法的时间效率取决于比较的次数。

命题 A：对于长度为 N 的数组，选择排序需要大约 N²/2次比较和 N 次交换
证明：通过查看代码我们可以精确的得到，0 到 N-1 的任意 i 都会进行一次交换和 N-1-i 次比较，因此总共有 N 次交换以及 (N-1)+(N-2)+...+2+1 = N(N-1)/2 ≈ N²/2

选择排序有两个鲜明特点：

运行时间和输入无关
移动数据最少：每次交换改变两个数组元素的值。共 N 次交换——交换次数和数组大小是线性关系。我们研究的其他任何算法都不具备这个特征（大部分的增长数量级都是线性对数或者平方级别）

3. 插入排序

通常人们整理桥牌的方法是一张一张的来，将每一张牌插入到其他已经有序的牌中的适当位置。
算法 1.2

class Insertion<Sortable>: Sort<Sortable> where Sortable: Comparable {
    override func sort(a: inout [Sortable]) {
        for i in 1..<a.count {
            for j in stride(from: i, to: 0, by: -1) {
                if less(v: a[j], w: a[j-1]) {
                    exch(a: &a, i: j, j: j-1)
                } else { break }
            }
        }
    }
}

算法 1.2：插入排序的轨迹

命题B：对于随机排列的长度为 N 且主键不重复的数组，平均情况下插入排序需要 ≈ N²/4 次比较以及 ≈ N²/4 次交换。最坏情况下需要 ≈ N²/2 次比较和 ≈ N²/2 次交换，最好情况下需要 N-1 次比较和 0 次交换。
证明：和命题 A 一样，通过一个 NxN 的轨迹表可以很容易就得到交换和比较次数。最坏情况下对角线之下的所有元素都需要移动位置，最好情况下都不需要。对于随机排列的数组，在平均情况下每个元素都可能向后移动半个数组的长度，因此交换总数是对角线之下的元素总数的1/2。
所有 (1+2+...+N-2+N-1)/2 = N(N-1)/4≈ N²/4

插入排序对于实际应用中常见的某些类型的非随机数组很有效。例如，对有序或者接近有序的数组进行进行排序时，插入排序能够立即发现每个元素已经在合适位置了，这是它的运行时间也是线性的。
下面是几种典型的部分有序的数组：

数组中每个元素距离它的最终位置都不远
一个有序的大数组接一个小数组
数组中只有几个元素的位置不正确

插入排序对这样的数组很有效，而选择排序则不然，事实上，当倒置数量很少时，插入排序很可能比本文其他任何算法都要快

要大幅提高插入排序的速度并不难，只需要在内循环中将较大元素都向右移而不总是交换两个元素（这样访问数组的次数就能减半）

总的来说，插入排序对于部分有序的数组十分高效，也很适合小规模数组，而且它们也是高级排序算法的中间过程，在学习高级排序算法时会再次接触插入排序。

4. 希尔排序

为展示初级排序算法的价值，我们学习一种基于插入排序的快速排序算法——希尔排序。因为插入排序只交换相邻元素，因此元素只能一点一点从一端移到另一端。希尔排序为了加快快速简单地改进了插入排序，交换不相邻的元素以对数组局部进行排序，并最终用插入排序将局部有序数组排序。

希尔排序的思想是使数组中任意间隔为 h 的元素都是有序的。这样的数组被称为 h 有序数组。换句话说，一个 h 有序数组就是 h 个互相独立的有序数组编织在一起组成的一个数组（见图 1.4.1）。在进行排序时，如果 h 很大，我们就能将元素移动到很远的地方，为了实现更小的 h 有序创造方便。用这种方式，对任意以 1 结尾的 h 序列，我们都能够将数组排序。算法 1.3 的实现使用了序列 1/2(3^k-1)，从 N/3 开始递减至 1。我们把这个序列成为递增序列。算法 1.3 实时计算了它的递增序列，另一种方式是将递增序列存储在一个数组中。

图1.4.1 一个 h 有序数组即一个由 h 个有序子数组组成的数组

算法 1.3

class Shell<Sortable>: Sort<Sortable> where Sortable: Comparable {
    override func sort(a: inout [Sortable]) {
        var h = 1
        let N = a.count
        while h < N/3 {
            h = 3*h+1
        }
        while h >= 1 {
            for i in h..<N {
                // 将a[i]插入到a[i-h], a[i-2*h], a[i-3*h]...
                for j in stride(from: i, to: h-1, by: -h) {
                    if less(v: a[j], w: a[j-h]) {
                        exch(a: &a, i: j, j: j-h)
                    } else {
                        break
                    }
                }
            }
            h = h/3
        }
    }
}

希尔排序的轨迹

实现希尔排序的一种方法是对于每个 h，用插入排序将 h 个子数组独立地排序。但因为子数组是相互独立的，一个更简单的方法是在 h 子数组中将每个元素交换到比它大的元素之前去（将比它大的元素向右移一格）。只需要在插入排序的代码中将移动元素的距离由 1 改为 h 即可。这样希尔排序的实现就转化为了一个类似插入排序但使用不同增量的过程，这个改进如下：

override func sort(a: inout [Sortable]) {
        var h = 1
        let N = a.count
        while h < N/3 {
            h = 3*h+1
        }
        while h >= 1 {
            for i in h..<N {
                let t = a[I]
                var j = I
                while j >= h && less(v: t, w: a[j-h]) {
                    a[j] = a[j-h]
                    j -= h
                }
                a[j] = t
            }
            h = h/3
        }
    }

我用一个 Int 类型 10000 个元素的随机数组进行排序测试，算法 1.3 的时间大概是 0.11s，改进后的运行时间大约为 0.8s，提高了大约 25%

如何选择递增序列呢（算法 1.3 使用 3 倍递增）？算法的性能不仅取决于 h，还取决于 h 之间的数学性质，比如它们的公因子等。很多论文研究了各种不同递增序列，但都无法证明某个序列是 “最好的”。算法 1.3 中的递增序列很简单，和复杂递增序列性能接近。但复杂递增序列在最坏的情况下由于算法 1.3。

和选择排序及插入排序相比，希尔排序可用于大型数组。它对任意排序（不一定随机）的数组表现都不错。下面是希尔排序可视轨迹图

图1.4.1：希尔排序的详细轨迹

研究希尔排序性能需要的数学论证超出本文的范围。如果你不相信，可以从证明当一个 “h有序”的数组按照增幅k排序之后，它任然是“h有序”的。算法 1.3 的运行时间达不到平方级别，例如它在最坏的情况下比较次数和 N^3/2成正比。

性质 E：使用递增序列1，4，13，40，121，364 ... 的希尔排序所需要的比较次数不会超出 N 的若干倍乘以递增序列的长度

5. 总结

我对一个 Int 类型 10000 个元素的数组分别使用选择排序、插入排序、希尔排序、和 swift 系统自带的排序比较如下：

let array = getArray()
Thread.sleep(forTimeInterval: 1)
let t1 = CFAbsoluteTimeGetCurrent()
Selection<Int>(args: array)
let t2 = CFAbsoluteTimeGetCurrent()
Insertion<Int>(args: array)
let t3 = CFAbsoluteTimeGetCurrent()
Shell<Int>(args: array)
let t4 = CFAbsoluteTimeGetCurrent()
array.sorted()
let tx = CFAbsoluteTimeGetCurrent()
print(t2-t1)
print(t3-t2)
print(t4-t3)
print(tx-t4)

打印结果

// 选择排序的运行时间
24.563407063484192
// 插入排序的运行时间
8.074509978294373
// 希尔排序的运行时间
0.07093596458435059
// swift 系统排序的运行时间
0.0352710485458374

系统排序的时间是最短的，但是我们可以发现希尔排序的时间确实要比选择排序和插入排序快太多。

二、归并排序

归并即将两个游戏数组归并为一个更大的有序数组。要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。你将会看到，归并排序最吸引人的性质是保证将任意长度为 N 的数组排序所需要的时间和 NlogN 成正比；它的主要缺点是需要额外空间和 N 成正比

归并排序示意图

1. 原地归并的抽象方法

实现归并的一种直接方法是将两个不同有序数组归并到第三个数组中，但是当用归并对大数组进行排序时，需要进行多次归并，如果每次都创建一个新数组，会带来性能问题，我们更希望有一种能够原地归并的方法，在数组中移动元素不需要额外空间

func merge(_ a: inout [Sortable], _ low: Int, _ mid: Int, _ high: Int) {
        // 将 a[low...mid] 和 a[mid+1...high] 归并
        var i = low
        var j = mid+1
        for k in low...high {
            aux[k] = a[k]
        }
        for k in low...high {
            if i > mid {
                a[k] = aux[j]
                j += 1
            } else if j > high {
                a[k] = aux[i]
                i += 1
            } else if (less(v: aux[j], w: aux[i])) {
                a[k] = aux[j]
                j += 1
            } else {
                a[k] = aux[i]
                i += 1
            }
        }
    }

上面的代码是 Merge 类的用来归并数组的方法，aux 是 Merge 的一个属性，用来保证每次归并只使用 aux 的空间，放在每次归并开辟新的数组空间。
方法在归并时进行了四个条件判断（上面代码第二个循环中的 4 个 if else）这四个判断分别代表的意思

if i > mid 表示左边的元素用尽开始取右边
if i > high表示右边的元素用尽开始取左边
if (less(v: aux[j], w: aux[i])) 表示右半边当前元素小于左半边取右边元素
else表示右半边当前元素大于左半边取左边元素

下面情况数组 [E, E, G, M, R, A, C, E, R, T] 调用 merge 方法的轨迹其中 low = 0; high = 9; mid = 4; i = 0; j = 5

步骤(k值)	i,j	进入分支	变换后的数组
0	0, 5	A < E 进入分支3 a[0]=A; j+1=6	[A,E,G,M,R,A,C,E,R,T]
1	0, 6	C < E 进入分支3 a[1]=C; j+1=7	[A,C,G,M,R,A,C,E,R,T]
2	0, 7	E == E 进入分支4 a[2]=E; i+1=1	[A,C,E,M,R,A,C,E,R,T]
3	1, 7	E == E 进入分支4 a[3]=E; i+1=2	[A,C,E,E,R,A,C,E,R,T]
4	2, 7	E < G 进入分支3 a[4]=E; j+1=8	[A,C,E,E,E,A,C,E,R,T]
5	2, 8	R > G 进入分支4 a[5]=G; i+1=3	[A,C,E,E,E,G,C,E,R,T]
6	3,8	R > M 进入分支4 a[6]=M; i+1=4	[A,C,E,E,E,G,M,E,R,T]
7	4,8	R == R 进入分支4 a[7]=R; i+1=5	[A,C,E,E,E,G,M,R,R,T]
8	5,8	i(5) > mid(4) 进入分支1 a[8]=R; j+1=9	[A,C,E,E,E,G,M,R,R,T]
9	5, 9	i(5) > mid(4) 进入分支1 a[9]=T; j+1=10	[A,C,E,E,E,G,M,R,R,T]

通过上面的轨迹我们可以看出函数 merge 的功能是将两个有序数组归并为一个有序的大数组，只有当我们给定的数组 a 将其子数组 a[low...high] 分割为 a[low...mid] 和 a[mid+1...high] 后，只有当 a[low...mid] 和 a[mid+1...high] 都为有序数组时，归并后的数组 a[low...high] 也为有序。

2. 自顶向下的并归排序

算法 1.4 基于原地归并的方法实现了另一种递归归并，这也是应用高效算法设计中分治思想的最典型的一个例子。这段递归代码是归纳证明算法能够正确地将数组排序的基础：如果它能将两个子数组排序，它就能通过归并两个子数组来将整个数组排序。
算法 1.4

class Merge<Sortable>: Sort<Sortable> where Sortable: Comparable {
    var aux: [Sortable] = []
    func merge(_ a: inout [Sortable], _ low: Int, _ mid: Int, _ high: Int) {
        // 将 a[low...mid] 和 a[mid+1...high] 归并
        var i = low
        var j = mid+1
        for k in low...high {
            aux[k] = a[k]
        }
        for k in low...high {
            if i > mid {
                a[k] = aux[j]
                j += 1
            } else if j > high {
                a[k] = aux[i]
                i += 1
            } else if (less(v: aux[j], w: aux[i])) {
                a[k] = aux[j]
                j += 1
            } else {
                a[k] = aux[i]
                i += 1
            }
        }
    }
    
    override func sort(a: inout [Sortable]) {
        aux = a
        sort(a: &a, low: 0, high: a.count-1)
        
    }
    
    func sort(a: inout [Sortable], low: Int, high: Int) {
        if high<=low {
            return
        }
        let mid = (low+high)/2
        sort(a: &a, low: low, high: mid)
        sort(a: &a, low: mid+1, high: high)
        merge(&a, low, mid, high)
    }
}

自顶向下的归并排序中归并结果的轨迹

上图是自顶向下的归并排序中归并结果的轨迹，如果在计算机上打印每次 merge 后的数组 a，就很容易发现算法 1.4 的执行顺序

我们也可以通过下面的树状图来理解算法 1.4 的执行过程

命题F：对于长度为 N 的任意数组，自顶向下的归并排序需要 1/2NlgN 至 NlgN 次比较
证明：另 C(N) 表示将一个长度为 N 的数组排序时所需要的比较次数。我们有 C(0)=C(1)=0，对于 N>0，通过递归的 sort() 方法我们可以由相应的归纳关系得到比较次数的上限：
C(N) <= C(⌊N/2⌋) + C(⌈N/2⌉) + N ----------(式1)
C(N) >= C(⌊N/2⌋) + C(⌈N/2⌉) + ⌊N/2⌋ -----(式2)

$\small{看 sort(a: low: high:) 方法}$
$\small{C(⌊N/2⌋) 代表 sort(a: \&a, low: low, high: mid)，N/2 向下取整}$
$\small{C(⌈N/2⌉) 代表 sort(a: \&a, low: mid+1, high: high)，N/2 向上取整}$
$\small{merge(\&a, low, mid, high) 的比较次数范围是 N ~ ⌊N/2⌋}$

当 N=2ⁿ 时，设 ⌈N/2⌉=⌊N/2⌋= 2^n-1
式1变换： C(2ⁿ) = 2C(2^n-1) + 2ⁿ
两遍同时除以2ⁿ：
C(2ⁿ)/2ⁿ = C(2^n-1)/2^n-1+1 = C(2^n-2)/2^n-2+1+1 ...
最后可以得到：
C(2ⁿ)/2ⁿ = C(2⁰)/2⁰+n
C(2ⁿ) = n2ⁿ
C(N) <= $N$ lg $N$
同理式2变换后为 C(N) >= 1/2 $N$ lg $N$

命题G：对于长度为 N 的任意数组，自顶向下的归并排序最多需要访问数组 6NlgN 次
证明：每次归并最多需要访问数组 6N 次（2次用来复制，2N次用来将排好的元素移动回去，另外最多比较 2N 次），根据命题 F 即可得到这个命题结果。

命题 F 和 G 告诉我们归并排序所需时间和 NlgN 成正比。它的主要缺点是辅助数组所使用的额外空间和 N 的大小成正比。我们可以通过一些细致的思考大幅缩短归并排序的运行时间。

2.1 对小规模数组使用插入排序

因为递归会使小规模问题中方法的调用过于频繁，所以我们在小规模数组时使用插入排序，会更快一些，将多么长的数组视为小规模的子数组对性能有较大影响这里我们选择 lgN 长度的数组。一般这种改进会将运行时间缩短 10% ~ 15%左右

class Merge<Sortable>: Sort<Sortable> where Sortable: Comparable {
    var aux: [Sortable] = []
    func merge(_ a: inout [Sortable], _ low: Int, _ mid: Int, _ high: Int) {
        // 实现请看算法 1.4
    }
    
    override func sort(a: inout [Sortable]) {
        aux = a
        let k = Int(log2(Double(a.count)))+2
        sort(a: &a, low: 0, high: a.count-1, k: k)
    }
    
    func sort(a: inout [Sortable], low: Int, high: Int, k: Int) {
        if high<=low {
            return
        }
        let mid = (low+high)/2
        if high-low+1 < k {
            insert(a: &a, low: low, high: high)
            return
        }
        sort(a: &a, low: low, high: mid, k: k)
        sort(a: &a, low: mid+1, high: high, k: k)
        merge(&a, low, mid, high)
    }
    func insert(a: inout [Sortable], low: Int, high: Int) {
        for i in (low+1)...high {
            let t = a[I]
            var j = I
            while j > low && less(v: t, w: a[j-1]) {
                a[j] = a[j-1]
                j-=1
            }
            a[j]=t
        }
    }
}

我使用 50 个元素的 Int 随机数组使用普通自顶向下的归并排序和本节的改进型运行时间分别为 15.57s、12.78s

2.2 测试数组是否已经有序

我们可以添加一个判断条件，如果 a[mid] 小于等于 a[mid+1]，我们就认为数组已经是有序的并跳过 merge 方法。这个改动不影响排序的递归调用，但是任意有序的子数组算法的运行时间就变为线性的了。

func sort(a: inout [Sortable], low: Int, high: Int, k: Int) {
        if high<=low {
            return
        }
        let mid = (low+high)/2
        if high-low+1 < k {
            insert(a: &a, low: low, high: high)
            return
        }
        sort(a: &a, low: low, high: mid, k: k)
        sort(a: &a, low: mid+1, high: high, k: k)
        if a[mid] <= a[mid+1] {
            return
        }
        merge(&a, low, mid, high)
    }

加了判断后对于随机的大数组排序时间并不会有所缩短，但是如果数组本身接近有序，会大大缩短排序时间

2.3 不将元素复制到辅助数组

我们可以节省将数组元素复制到用于归并的辅助数组所用的时间（但空间不行）。要做到这一点我们要调用两种排序方法，一种将数据从输入数组排序到辅助数组，一种将数据从辅助数组排序到输入数组。这种方法需要一些技巧，我们要在递归调用的每个层次交换输入数组和辅助数组的角色。

3. 自底向上的归并排序

override func sort(a: inout [Sortable]) {
        aux = a
        let N = a.count
        var sz = 1
        while sz < N {
            var lo = 0
            while lo < N-sz {
                merge(&a, &aux, lo, lo+sz-1, min(lo+2*sz-1, N-1))
                lo += 2*sz
            }
            sz *= 2
        }
    }

自底向上的归并排序结果

三、快速排序

快速排序引人注目的特点包括它是原地排序（只需要一个很小的辅助栈），且将长度为 N 的数组排序所需要的时间和 NlgN 成正比。另外快速排序的内循环币大多数排序算法都要小，这意味着它无论是理论上还是在实际中都要更快。它的主要缺点是非常脆弱，在实现时要非常小心才能避免低劣的性能。已经有无数例子显示许多错误都能致使它在实际中的性能只能有平方级。

1. 基本算法

快速排序是一种分治的排序算法。它将一个数组分成两个子数组，将两部分独立排序。快速排序和归并排序是互补的：快速排序将数组排序的方式则是当两个子数组都有序时整个数组页就自然有序了。在快速排序中切分的位置取决于数组的内容。大致过程如下：

快速排序示意图

算法 1.5

class Quick<Sortable>: Sort<Sortable> where Sortable: Comparable {
    override func sort(a: inout [Sortable]) {
        a.shuffle()
        sort(a: &a, low: 0, high: a.count-1)
    }
    
    func sort(a: inout [Sortable], low: Int, high: Int) {
        if high <= low {
            return
        }
        let j = partition(a: &a, low: low, high: high)
        sort(a: &a, low: low, high: j-1)
        sort(a: &a, low: j+1, high: high)
    }
    
    func partition(a: inout [Sortable], low: Int, high: Int) -> Int {
        var i = low
        var j = high+1
        let v = a[low]
        while true {
            repeat {
                i += 1
                if i == high {
                    break
                }
            } while less(v: a[i], w: v)
            
            repeat {
                j -= 1
                if j == low {
                    break
                }
            } while less(v: v, w: a[j])
            if i >= j {
                break
            }
            exch(a: &a, i: i, j: j)
        }
        exch(a: &a, i: low, j: j)
        return j
    }    
}

快速排序递归地将子数组 a[low...high] 排序，先用 partition() 方法将 a[j] 放到一个合适的位置，然后递归调用将其他位置的元素排序。
partition() 的作用：从左到右找到一个大于 a[low] 的元素和从右往左找到的一个小于 a[low] 的元素交换，直到左边大于等于右边，然后将第 low 个元素放到适当位置，并返回这个位置

对于某个 j，a[j] 已经排定；
a[low] 到 a[j-1] 中所有元素都不大于 a[j]；
a[j+1] 到 a[high] 中所有元素都不小于 a[j]。

它是一个随机化的算法，因为它在将数组排序之前将其随机打乱。我们这么做的原因是希望能够预测（并依赖）该算法的性能特性。

快速排序的切分示意图

切分轨迹

下面是几个细节问题，它们都可能导致实现错误或者影响性能
1、原地切分：如果使用一个辅助数组，很容易实现切分，但将切分后的数组复制回去的开销也许会使我们得不偿失。

2、别越界：如果切分元素是数组中最小或者最大的那个元素，我们就要小心别让扫描指针跑出数组边界

3、保持随机性：数组元素的顺序是被打乱过的。因为算法 1.5 对所有的子数组都一视同仁，它的所有子数组页都是随机排序的。这对于预测算法的运行时间很重要。保持随机性的另一种方法是在 partition() 中随机选择一个切分元素。

4、终止循环：正确的检测指针是否越界需要一点技巧。一个最常见的错误是没有考虑到数组中可能包含和切分元素值相同的其他元素。

5、处理切分元素值有重复的情况：如算法 1.5 所示，左侧扫描最好是在遇到大于等于切分元素时停下，右侧则是在小于等于切分元素时停下。尽管这样可能会不必要的将一些等值进行交换，但在某些典型应用中，它能够避免算法的运行时间变为平方级。

6、终止递归：实现快速排序时一个常见的错误就是不能保证切分元素放入正确的位置，从而导致程序在切分元素正好是子数组的最大或者最小元素时陷入无限循环之中。

2. 性能特点

快速排序切分方法的内循环会用一个递增的索引将数组元素和一个定值比较。这种简洁性也是快速排序的一个优点，很难想象排序算法还能有比这更短小的内循环了。例如，归并排序和希尔排序一般都比快速排序慢，其原因就是它们在内循环中移动数据。
快速排序另一个优势在于它的比较次数很少。排序效率最终还是依赖切分数组的效果，而这依赖于切分元素的值。切分将一个较大的随机数组分成两个随机子数组，而实际上这种分割可能发生在数组的任意位置(对于元素不重复的数组而言)。下面我们分享这个算法和理想方法之间的差距
快速排序的最好情况是每次都正好将数组对半分

命题K：将长度为 N 的无重复数组排序，快速排序平均需要 ≈ 2NlnN ≈ 1.39NlgN次比较（以及 1/6 的交换）。
也就是说平均比较次数只比最好情况多 39%
命题L：快速排序最多需要 N²/2 次比较，但随机打乱数组能够预防这种情况。

3. 算法改进

几乎从 Hoare 第一次发表这个算法开始，人们就不断提出各种改进方法。并不是所有的想法都可行，因为快速排序的平衡性已经非常好，改进所带来的提高可能会被意外的副作用所抵消。但其中一些，非常有效。
你需要通过实验来确定改进的效果并为实现选择最佳参数。一般来说性能能提升 20% ~ 30%

3.1 切换到插入排序

和大多数递归排序算法一样，对于小数组，快速排序比插入排序慢。因为递归，快速排序的 sort() 方法在小数组中也会调用自己。

3.2 三取样切分

改进快速排序性能的第二个办法是使用子数组的一小部分元素的中位数来切分数组。这样做得到的切分更好，但代价需要计算中位数。人们发现取样大小设为 3 并用大小居中的元素切分的效果最好。

3.3 熵最优的排序

实际应用中经常会出现含有大量重复元素的数组，例如将大量人员资料按照生日或者性别排序，在这些情况下，我们实现的快速排序的性能尚可，但还有巨大的改进空间。例如，在有大量重复元素的情况下，快速排序的递归性能会使元素全部重复的子数组经常出现，这就有很大改进潜力。
一个简单的想法是将数组切分为三个部分，分别对应小于，等于和大于切分元素的数组元素。这种切分实现起来比我们目前使用的二分法更复杂。

四、优先队列

许多应用程序都需要处理有序元素，但不一定要求它们全部有序，或是不一定要一次就将它们排序。很多情况下我们会手机一些元素，处理当前键值最大的元素，然后再收集更多的元素，再处理当前键值最大的元素，如此这般。例如，你有可能有一台能够同时运行多个应用程序的电脑（或者手机）。这是通过为每个应用程序的事件分配一个优先级，并总是处理下一个优先级最高的事件来实现的。例如，绝大多数手机分配给来点的优先级都会比游戏程序的高。
在这种情况下，一个合适的数据结构应该支持两种操作：删除最大元素和插入元素。这种数据类型叫做优先队列。优先队列的使用和队列（删除最老的元素）以及栈（删除最新的的元素）类似，但高校的实现它则更具挑战性。
这里简单讨论优先队列的基本表现形式（其一或者两种操作都能在线性时间内完成）之后，我们会学习基于二叉堆数据结构的一种优先队列的经典实现方法，用数组保存元素并按照一定条件排序，以实现高效的（对数级别的）删除最大元素和插入元素操作。
优先队列的一些重要的应用场景包括模拟系统，其中事件的键即为发生的时间，而系统需要按照时间顺序处理所有事件；任务调度，其中键值对应的优先级决定了应该首先执行哪些任务；数值计算，键值代表计算错误，而我们需要按照键值指定的顺序来修正它们。
通过插入一列元素然后一个个地删掉其中最小的元素，我们可以用优先队列实现排序算法。一种名为堆排序的重要排序算法也来自于基于堆的优先队列的实现。

1. API

优先队列是一种抽象数据类型，它表示一组值和对这些值的操作，它的抽象层使我们能够方便地将应用程序和我们将学习的各种具体实现隔离开来。我们会详细定义一组应用程序编程接口（API）来为数据结构的用例提供足够的信息。优先队列最重要的操作就是删除最大元素和插入元素，所有我们会把精力集中在它们身上。和排序算法一样。如果允许重复元素，最大表示的是所有最大元素之一。为了将 API 定义完整，我们还需要加入构造函数（和我们在栈以及队列中使用的类似）和一个空队列测试方法。

1.1、优先队列的调用示例

为了展示优先队列的抽象模型的价值，考虑以下问题：输入 N 个字符串，每个字符串都对应着一个整数，你的任务就是从中找出最大的（或是最小的）M 个整数（及其关联的字符串）。这些输入可能是金融事务，你需要从中找出最大的那些；或是农产品杀虫剂含量，这时你需要从中找到最小的那些；或是服务请求、科学实验的结果，或是其他应用。在某些应用场景中，输入量可能非常巨大，甚至可以认为输入是无限的。解决这个问题的一种方法是将输入排序然后从中找出 M 个最大的元素，但我们已经说明输入将会非常庞大。另一种方法是将每个新的输入和已知的 M 个最大元素比较，但除非 M 较小，否则这种比较的代价会非常高昂。
$\small{从 N 个输入中找到 M 个元素所需成本}$

示例	时间	空间
排序算法的用例	NlogN	N
初级实现的优先队列	NM	M
基于堆实现的优先队列	NlogM	M

2. 初级实现

2.1 数组实现（无序）

或许实现优先队列的最简单方法就是基于 (一) 中的下压栈代码。insert() 方法的代码和栈的 push() 方法完全一样。要实现删除最大元素，我们可以添加一段类似于选择排序的内循环的代码，将最大元素和边界元素交换然后删除它，和我们对栈的 pop() 方法的实现一样。和栈类似，我们也可以加入调整数组大小的代码来保证数据结构至少含有四分之一的元素而又永远不会溢出。

2.2 数组实现（有序）

另一种方法就是在 insert() 方法中添加代码，将所有较大的元素向右移动一格以使数组保持有序（和插入排序一样）。这样最大的元素总会在数组的一边，优先队列删除最大元素操作就和栈的 pop() 操作一样了。

2.3 链表表示法

和刚才类似，我们可以基于链表的下压栈的代码作为基础，然后可以选择修改 pop() 来找到并返回最大元素，或是修改 push() 来保证所有元素为逆序并用 pop() 来删除并返回链表的首元素（也就是最大的元素）
使用无序序列是解决这个问题的惰性方法，我们仅在必要的时候才会采取行动；使用有序序列则是解决问题的积极方法，因为我们会尽可能未雨绸缪（在插入元素时就保持列表有序），使后续操作更高效。
实现栈或者是队列与实现优先队列的最大不同在于对性能的要求。对于栈和队列，我们的实现能够在常数时间内完成所有操作；而对于优先队列，我们刚才讨论的所有初级实现中，插入元素和删除最大元素这两个操作之一在最坏情况下需要线性时间来完成。我们接下来要讨论的基于数据结构堆的实现能够保证这种操作都能更快的执行。

数据结构	插入元素	删除最大元素
有序数组	N	1
无序数组	1	N
堆	logN	logN
理想情况	1	1

3. 堆的定义

数据结构二叉堆能够很好的实现优先队列的基本操作。在二叉堆的数组中，每个元素都要保证大于等于另两个特定位置的元素。相应的，这些位置的元素又至少要大于等于数组中的另两个元素，以此类推。如果我们将所有元素画成一棵二叉树，将每个较大元素和两个较小元素用边连接就可以很容易看出这种结构

定义：当一棵二叉树的每个结点都大于等于它的两个子节点时，它被称为堆有序。

相应地，在堆有序的二叉树中，每个结点都小于等于它的父结点（如果有的话）。从任意结点向上，我们都能够得到一列非递减的元素；从任意结点向下。我们都能得到一列非递增的元素。特别的：

命题O：根节点是堆有序二叉树的最大结点。

3.1 二叉堆表示法

一棵堆有序的完全二叉树

如果我们用指针来表示堆有序的二叉树，那么每个元素都需要三个指针来找到它的上下结点（父结点和两个子结点各需要一个）。但如上图所示，如果我们使用完全二叉树，表达就会变得特别方便。要画出这样一颗完全二叉树，可以先定下根节点，然后一层一层的由上向下、从左至右，在每个结点的下方连接两个更小的结点，直至将 N 个结点全部连接完毕。完全二叉树只用数组而不需要指针就可以表示。具体方法就是将二叉树的结点按照层级顺序放入数组中，根结点的位置 1，它的子节点的位置 2 和 3，而子结点的子结点则分别在 4、5、6 和 7，以此类推。

定义：二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级存储（不使用数组的第一个位置）。

（在下文中我们将二叉堆简称为堆）在一个堆中，位置 k 的结点的父结点的位置为⌊k/2⌋，而它的两个子结点的位置则分别为 2k 和 2k+1。
用数组（堆）实现的完全二叉树的结构是很严格的，但它的灵活性已经足以让我们高效的实现优先队列。用它们将能实现对数级别的插入元素和删除元素操作。利用在数组中无需指针即可沿树上下移动的便利和以下性质，算法保证了对数复杂度的性能。

命题P：一棵大小为 N 的完全二叉树的高度为 ⌊lgN⌋

堆的表示

4. 堆的算法

我们会使用更加紧凑的实现方式，不再将数组作为参数传递。堆的操作会首先进行一些简单的改动，打破堆的状态，然后再遍历堆并按照要求将堆的状态恢复。我们称这个过程叫做堆的有序化。
在有序化的过程中会有两种情况。当某个结点的优先级上升（或是在堆底加入一个新的元素）时，需要由下至上恢复堆的顺序。当某个结点的优先级下降（例如，将根节点替换为一个较小的元素）时，我们需要由上至下恢复堆的顺序。首先，我们会学习如何实现这两种辅助操作，然后再用它们实现插入元素和删除最大元素的操作。

4.1 由下至上的堆有序化（上浮）

private func swim(_ k: Int) {
    var i = k
    while i > 1 && less(i/2, i) {
        exch(i/2, i)
        i = I/2
    }
}

如果堆有序的状态因为某个结点变得比它的父结点更大而被打破，就是原本的堆数组是堆有序的，但是 k 点的值变得比父结点大了，那么就用上面的方法进行上浮操作后，堆就会再次变得有序，上浮过程如下图

由下至上的堆有序化（上浮）

4.2 由上至下的堆有序化（下沉）

    private func sink(_ k: Int) {
        var i = k
        while i*2 <= N {
            var j = 2*I
            if j < N && less(j, j+1) {
                j = j+1
            }
            if !less(i, j) {
                break
            }
            exch(i, j)
            i = j
        }
    }

如果堆的有序状态因为某个结点变得比它的两个子节点或者是其中之一更小了而被打破，那么可以通过将它的两个子结点中的较大者交换来恢复堆。就是原本的堆数组是堆有序的，但是 k 点的值变得比子结点小了，那么就用上面的方法进行下沉操作后，堆就会再次变得有序，下沉过程如下图：

由上至下的堆有序化（下沉）

sink() 和 swim() 方法是高效实现优先队列 API 的基础，原因如下
插入元素：我们将新元素加到数组末尾，增加堆的大小并让这个新元素上浮到合适的位置
删除最大元素：我们从数组顶端删去最大的元素并将数组的最后一个元素放到顶端，减小堆的大小并让这个元素下沉到合适的位置。
算法 1.6 解决了我们在本节开始时提出的一个基本问题：它对优先队列 API 的实现能够保证插入元素和删除最大元素这两个操作的用时和队列的大小仅成对数关系。
算法 1.6

class MaxPQ<Element> where Element: Comparable {
    private var pq: [Element?] = [nil];
    private var N: Int {
        return pq.count-1;
    }
    private var maxN: Int = 0
    
    init(_ maxN: Int) {
        self.maxN = maxN
    }
    
    func insert(_ v: Element) {
        if N == maxN {
            return
        }
        pq.append(v)
        swim(N)
    }
    
    func max() -> Element? {
        if isEmpty {
            return nil
        }
        return pq[1]
    }
    func delMax() -> Element? {
        if isEmpty {
            return nil
        }
        let max = pq[1]
        exch(1, N);
        pq.removeLast()
        sink(1)
        return max
    }
    
    var isEmpty: Bool {
        return N == 0
    }
    
    var size: Int {
        return N
    }
    
    private func swim(_ k: Int) {
        var i = k
        while i > 1 && less(i/2, i) {
            exch(i/2, i)
            i = I/2
        }
    }
    
    private func sink(_ k: Int) {
        var i = k
        while i*2 <= N {
            var j = 2*I
            if j < N && less(j, j+1) {
                j = j+1
            }
            if !less(i, j) {
                break
            }
            exch(i, j)
            i = j
        }
    }
    
    private func exch(_ i: Int, _ j: Int) {
        let t = pq[i]
        pq[i] = pq[j]
        pq[j] = t
    }
    private func less(_ i: Int, _ j: Int) -> Bool {
        return pq[i]! < pq[j]!
    }
}

堆的操作

命题Q：对于一个含有 N 个元素的基于堆的优先队列，插入元素操作只需要不超过 lgN+1 次比较，删除最大元素的操作需要不超过 2lgN 次比较

使用有序或是无序数组的优先队列的初级实现总是需要线性时间来完成其中一种操作，但基于堆的实现能够保证在对数时间内完成它们。这种差别使得我们能够解决以前无法解决的问题

在堆上的优先队列操作

4.3 多叉堆

基于用数组表示的完全三叉数结构堆并修改相应的代码并不困难。对于数组中 1 至 N 的 N 个元素，位置 k 的结点大于等于位于 3k-1、3k 和 3k+1 的结点，小于等于位于⌊(k+1)/3⌋ 的结点。甚至对于给定的 d，将其修改为任意的 d 叉树也不困难。我们需要在树高（log_dN）和在每个结点的 d 个子结点找到最大者的代价之间找到折中，这取决于实现的细节以及不同操作的预期相对频繁程度。

4.4 调整数组大小

我们可以添加一个没有参数的构造函数，在 insert() 中添加将数组长度加倍的代码，在 delMax() 中添加将数组长度减半的代码，这样，算法的用例就无须关注各种队列大小的限制。当优先队列的数组大小可以调整、队列长度可以是任意值时，命题 Q 指出的对数时间复杂度上限就是针对一般性的队列长度 N 而言了

4.5 元素的不可变性

优先队列存储了用例创建的对象，但同时假设用例代码不会改变它们（改变它们就可能打破堆的有序性）。我们可以将这个假设转化为强制条件，但程序员通常不会这么做，因为增加代码的复杂性会降低性能。

4.6 索引优先队列

在很多应用中，允许用例引用已经进入优先队列中的元素是必要的。做到这一点的一种简单方法是给每个元素一个索引。另外，一种常见的情况是用例已经有了总量为 N 的多个元素，而且可能还同时使用了多个（平行）数组来存储这些元素的信息。此时，其他无关的用例代码可能已经在使用一个整数索引来引用这些元素了。

IndexMinPQ 的属性和方法	意义
init(maxN: Int)	创建一个最大容量为 maxN 的优先队列，索引取值范围为 0 至 maxN-1
insert(k: Int, item: Item)	插入一个元素，将它和索引 k 相关联
change(k: Int, item: Item)	将索引为 k 的元素设为 item
contains(k: Int)->Bool	是否存在索引为 k 的元素
delete(k: Int)	删去索引 k 及其相关联的元素
min()->Item?	返回最小元素
minIndex()->Int?	返回最小元素的索引
delMin()->Int?	删除最小元素，并返回它的索引
isEmpty()->Bool	优先队列是否为空
size()->Int	优先队列中的元素数量

理解这种数据结构的一个较好方法是将它看成一个能够快速访问其中最小元素的数组。事实上它还要更好——它能够快速访问数组的一个特定子集中的最小元素（指所有被插入的元素）。换句话说，可以将名为 pq 的 IndexMinPQ 类优先队列看做数组 pq[0...N-1] 中的一部分元素的代表。将qp.insert(k, item) 看做将 k 加入这个子集并使 pq[k] = item，qp.change(k, item) 则代表令 pq[k] = item。这两种操作没有改变其他操作所依赖的数据结构，其中最重要的就是 delMin() 和 change() 这些操作在许多应用中都很重要并且依赖于元素的引用。

命题Q（续）：在一个大小为 N 的索引优先队列中，插入元素、改变优先级、删除和删除最小元素操作所需的比较次数和 logN 成正比

操作	比较次数的增长数量级
insert()	logN
change()	logN
contains()	1
delete()	logN
min()	1
minIndex()	1
delMin()	logN

4.7 索引优先队列的用例

下面的用例调用了 IndexMinPQ 的代码 Multiway 解决了多项归并问题：它将多个有序的输入流归并成一个有序的输出流。许多应用中都会遇到这个问题。输入可能来自于多种科学仪器的输出，或是来自多个音乐或电影网站的信息列表，或是商业交易等。如果有足够的空间，你可以把它们简单地读入一个数组并排序，但如果用了优先队列，无论输入有多长你都可以把它们全部读入并排序

5. 堆排序

我们可以把任意优先队列变成一种排序方法。将所有元素插入一个查找最小元素的优先队列，然后再重复调用删除最小元素的操作用来将它们按顺序删去。用无序数组实现的优先队列这么做相当于进行一次插入排序。用基于堆的优先队列这样做等同于那种排序？一种全新的排序方法！下面我们用堆实现一种经典而优雅的排序算法——堆排序
堆排序可以分为两个阶段。在堆的构造阶段，我们将原始数组重新组织安排进一个堆中；然后在下沉排序阶段，我们从堆中按递减顺序取出所有元素并得到排序结果。

lass PQSort<Sortable>: Sort<Sortable> where Sortable: Comparable {
    override func sort(a: inout [Sortable]) {
        let pq = MinPQ<Sortable>(a.count)
        for v in a {
            pq.insert(v)
        }
        var i = 0
        while pq.N > 0  {
            a[i] = pq.delMin()!
            i += 1
        }
    }
}

class MinPQ<Element> where Element: Comparable {
    private var pq: [Element?] = [nil];
    var N: Int {
        return pq.count-1;
    }
    private var maxN: Int = 0
    
    init(_ maxN: Int) {
        self.maxN = maxN
    }
    
    func insert(_ v: Element) {
        pq.append(v)
        swim(N)
    }

    func delMin() -> Element? {
        let min = pq[1]
        exch(1, N);
        pq.remove(at: N)
        sink(1)
        return min
    }
    
    private func swim(_ k: Int) {
        var i = k
        while i > 1 && less(i, i/2) {
            exch(i/2, i)
            i = i/2
        }
    }
    
    private func sink(_ k: Int) {
        var i = k
        while i*2 <= N {
            var j = 2*i
            if j < N && less(j+1, j) {
                j = j+1
            }
            if less(i, j) {
                break
            }
            exch(i, j)
            i = j
        }
    }
    
    private func exch(_ i: Int, _ j: Int) {
        let t = pq[i]
        pq[i] = pq[j]
        pq[j] = t
    }
    private func less(_ i: Int, _ j: Int) -> Bool {
        return pq[i]! < pq[j]!
    }
}

命题S：将 N 个元素排序，堆排序只需要少于（2NlgN + 2N）次比较（以及一半次数的交换）

算法 第4版(塞奇威克)学习——排序