主讲人： 吕敏 Email: { lvmin05@ustc.edu.cn } Spring 2012 ，USTC 算法基础 主讲人： 吕敏 Email: { lvmin05@ustc.edu.cn } Spring 2012 ，USTC

第六讲 排序 内容提要： 排序问题 堆排序算法 快速排序算法 线性时间排序 排序算法比较 2018/11/20 2

第六讲 排序 内容提要： 排序问题 堆排序算法 快速排序算法 线性时间排序 排序算法比较 2018/11/20 3

排序问题 问题描述： 输入数据的结构可以各种各样，比如n元数组、链表等； 排序问题是计算机科学领域中的最基本问题： 输入：n个数的序列 输出：输入序列的一个重排 ，使得 输入数据的结构可以各种各样，比如n元数组、链表等； 排序问题是计算机科学领域中的最基本问题： 有些应用程序本身就需对信息进行排序； 应用广泛，是许多算法的关键步骤； 已有很多成熟算法，它们采用各种技术，具有历史意义； 可以证明其非平凡下界，是渐近最优的； 可通过排序过程的下界来证明其他一些问题的下界； 在实现过程中经常伴随着许多工程问题出现（主机存储器层次结构、软件环境等） 2018/11/20 4

排序问题 当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。 排序的稳定性： 在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的； 若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。 排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。 2018/11/20 5

第六讲 排序 内容提要： 排序问题 堆排序算法 快速排序算法 线性时间排序 排序算法比较 2018/11/20 6

堆排序 堆排序（heapsort）结合了插入排序与合并排序的优点。 运行时间与合并排序一致：O(nlgn) 和插入排序都是一种原地排序算法：在排序输入数组时，只有常数个元素存储在输入数组之外。 堆排序引入了一种算法设计技术：利用了一种重要的数据结构——“堆”——来管理算法执行中的信息。

堆数据结构 堆数据结构是一种数组对象，可以被视为一棵完全二叉树。树中每个节点与数组中存放该结点值的那个元素对应。树的每一层都是填满的，最后一层可能除外（从一个结点的左子树开始填） 表示堆的数组对象A具有两个性质： length[A]：是数组中的元素个数； heap-size[A]: 是存放在A中的堆得元素个数； heap-size[A] ≤ length[A] 16 1 14 2 10 3 8 4 7 5 9 6 1 2 3 4 5 6 7 8 9 10 16 14 2018/11/20 8

堆数据结构 作为数组对象的堆，给定某个结点的下标i，则： 堆的分类： 在堆排序算法中，我们使用大根堆，堆中最大元素位于树根； 父节点PARENT( i ) = floor( i /2 ), 左儿子为LEFT( i ) = 2 i，右儿子为RIGHT( i ) = 2 i + 1; 堆的分类： 大根堆（最大堆）：除根节点之外的每个节点i，有 即某结点的值不大于其父结点的值，故堆中的最大元素存放在根结点中。 小根堆（最小堆） ：除根节点之外的每个节点i，有 即某结点的值不小于其父结点的值，故堆中的最小元素存放在根结点中。 在堆排序算法中，我们使用大根堆，堆中最大元素位于树根； 最小堆通常在构造优先队列时使用。 2018/11/20 9

堆数据结构 视为完全二叉树的堆： 堆结构的基本操作： 结点在堆中的高度定义为从本结点到叶子的最长简单下降路径上边的数目； 定义堆的高度为树根的高度； 具有n个元素的堆其高度为Ө( lg n )； 堆结构的基本操作： MAX-HEAPIFY，运行时间为O( lg n )，保持最大堆性质； BUILD-MAX-HEAP，以线性时间运行，可以在无序的输入数组基础上构造出最大堆； HEAPSORT，运行时间为O( nlgn )，对一个数组进行原地排序； MAX-HEAP-INSERT, HEAP-EXTRACT-MAX, HEAP-INCREASE-KEY 和 HEAP-MAXIMUM过程的运算时间为O( lg n ), 可以让堆结构作为优先队列使用； 2018/11/20 10

保持堆性质 MAX-HEAPIFY函数的输入为一个数组A和小标i。假定以LEFT( i ) 和RIGHT( i )为根的两棵二叉树都是最大堆，MAX-HEAPIFY让A[ i ]在最大堆中“下降”，使以i为根的子树成为最大堆。 MAX-HEAPIFY( A, i ) 1 l ← LEFT( i ); 2 r ← RIGHT( i ); if l ≤ heap-size[A] and A[ l ] > A[ i ] then largest ← l else largest ← i if r ≤ heap-size[ A] and A[ r ] > A[ largest ] then largest ← r if largest ≠ I then exchange A[ i ] ↔ A[ largest ] MAX-HEAPIFY( A, largest ) 2018/11/20 11

保持堆性质 16 1 14 2 10 3 4 7 5 9 6 8 i 16 1 4 2 10 3 14 7 5 9 6 8 i 16 1 14 2 10 3 8 4 7 5 9 6 i 2018/11/20 12

保持堆性质 基本思想： 1）找出A[ i ], A[LEFT( i )]和A[RIGHT( i )]中最大者，将其下标存在largest； 2）交换A[i]和A[largest]使得结点i和其子女满足最大堆性质； 3）下标为largest的结点在交换后的值是A[ i ]，以该结点为根的子树有可能违反最大堆性质，对该子树递归调用MAX-HEAPIFY; 2018/11/20 13

保持堆性质 时间复杂度分析： 当MAX-HEAPIFY作用在一棵以结点i为根的、大小为n的子树上时，其运行时间为调整元素A[i]、A[LEFT(i)]和A[RIGHT(i)]的关系时所用时间Ө(1)，再加上对以i的某个子节点为根的子树递归调用MAX-HEAPIFY所需的时间。i结点的子树大小最多为2n/3（此时，最底层恰好半满），运行时间递归表达式为： 根据主定理，该递归式的解为 即：MAX-HEAPIFY作用于一个高度为h的结点所需的运行时间为 2018/11/20 14

建堆操作 输入是一个无序数组A，BUILD-MAX-HEAP把数组A变成一个最大堆（自底向上），伪代码如下： 基本思想：数组A[ (n/2 +1) … n ]中的元素都是树中的叶子结点，因此每个都可以看作是只含一个元素的堆。BUILD-MAX-HEAP对数组中每一个其它内结点从后往前都调用一次MAX-HEAPIFY。 BUILD-MAX-HEAP ( A ) 1 heap-size[A] ← length[A]; for i ← FLOOR( length[A]/2 ) downto 1 do MAX-HEAPIFY( A, i ) 2018/11/20 15

建堆操作 2018/11/20 16

建堆操作 时间复杂度分析： 在树中不同高度的结点处运行MAX-HEAPIFY的时间不同，其作用在高度为h的结点上的运行时间为O(h)，故BUILD-MAX-HEAP时间代价为： 这说明，BUILD-MAX-HEAP可以在线性时间内，将一个无序数组建成一个最大堆。 2018/11/20 17

堆排序算法 基本思想： 调用BUILD-MAX-HEAP将输入数组A[1…n]构建成一个最大堆； 互置A[1]和A[n]位置，使得堆的最大值位于数组正确位置； 减小堆的规模； 重新调整堆，保持最大堆性质。 HEAPSORT( A ) 1 BUILD-MAX-HEAP(A) 2 for i ← length[A] downto 2 3 do exchange A[1] ↔ A[i] 4 heap-size[A] ← heap-size[A] -1 5 MAX-HEAPIFY( A, 1) 2018/11/20 18

堆排序算法 2018/11/20 19

堆排序算法 时间复杂度分析： 调用BUILD-MAX-HEAP时间为O(n), n-1次MAX-HAPIFY调用的每一次时间代价为O(lgn)。 HEAPSORT过程的总时间代价为：O(nlgn)。 是一种原地排序算法 思考：堆排序算法与插入排序算法设计策略关系是否类似？ （减治法：不断减小被处理的问题规模） 2018/11/20 20

优先级队列 优先级队列是一种用来维护由一组元素构成的集合S的数据结构，这一组元素中的每一个都有一个关键字Key。 一个最大优先级队列支持以下操作： INSERT(S, x)：把元素x插入集合S中； MAXIMUM(S)：返回S中具有最大关键字的元素； EXTRACT-MAX(S)：去掉并返回S中的具有最大关键字的元素； INCREASE-KEY(S, x, k)：将元素x的关键字的值增加到k，这里k值不能小于x的原始关键字的值。 最大优先级队列经常被用于分时计算机上的作业调度 2018/11/20 21

优先级队列 最大优先级队列经常被用于分时计算机上的作业调度，对要执行的各作业及他们之间的相对优先关系加以记录。 一个作业做完或被中断时，可用EXTRACT-MAX操作从所有等待的作业中，选择出具有最高优先级的作业。 任何时候，一个新作业都可用INSERT加入到队列中去。 最小优先级队列支持的操作： INSERT， MINMUM，EXTRACT-MIN， DECREASE-KEY 可被用在基于事件驱动的模拟器中。 事件模拟要按照各事件发生时间的顺序进行 每一步都使用EXTRACT-MIN选择下一个模拟的事件 一个新事件产生时，使用INSERT将其放入队列中。

优先级队列 MAXIMUN EXTRACT-MAX，运行时间为O(lgn) HEAP-MAXIMUM( A ) 1 return A[1] HEAP-EXTRACT-MAX( A ) if heap-size[A] < 1 then error “heap underflow” max ← A[1] A[1] ← A[heap-size[A]] heap-size[A] ← heap-size[A] – 1; MAX-HEAPIFY( A, 1 ) return max 2018/11/20 23

优先级队列 INCREASE-KEY：运行时间为O(lgn) INSERT: 运行时间为O(lgn) 一个堆可以在O(lgn)时间内，支持大小为n的集合上的任意优先队列操作。 HEAP-INCREASE-KEY(A, i, key ) if key < A[i] then error “new key is smaller than current key” A[ i ] ← key while i > 1 and A[PARANT(i)] < A[i] do exchange A[i ] ↔ A[PARANT(i)] i ← PARANT(i) MAX-HEAP-INSERT(A, key ) heap-size[A] ← heap-size[A] + 1 A[heap-size[A]] ← -∞ HEAP-INCREASE-KEY( A, heap-size[A], key ) 2018/11/20 24

第六讲 排序 内容提要： 排序问题 堆排序算法 快速排序算法 线性时间排序 排序算法比较 2018/11/20 25

快速排序算法 x A[p..q-1] A[q+1..r] q 快速排序是C.R.A.Hoare于1962年提出的一种地排序算法。对于包含n个数的输入数组，最坏情况运行时间为Ө(n2)，期望运行时间为Ө(nlgn)且常数因子较小。 基本思想是采用了一种分治的策略把未排序数组分为两部分，然后分别递归调用自身进行排序： 分解：数组A[p…r]被划分为两个（可能空）子数组A[p…q-1]和A[p+1..r]，使得A[p…q-1]中每个元素都小于或等于A[q]和A[q+1..r]中的元素。下标q在这个划分过程中进行计算； 解决：递归调用快速排序，对子数组A[p...q-1]和A[q+1..r]排序； 合并：不需要任何操作。 x A[p..q-1] A[q+1..r] q 2018/11/20 26

快速排序算法 快速排序伪代码： 数组划分过程PARTITION是QUICKSORT算法的关键，它对子数组A[p..r]进行就地排序。 * 为排序一个完整数组，最初调用 QUICKSORT(A, 1, length[A])。 数组划分过程PARTITION是QUICKSORT算法的关键，它对子数组A[p..r]进行就地排序。 QUICKSORT(A, p, r ) if p < r then q ← PARTITION(A, p, r ) QUICKSORT( A, p, q-1 ) QUICKSORT( A, q+1, r ) 2018/11/20 27

快速排序算法 数组划分过程 PARTITION p i j r x ≤ x > x unrestricted PARTITION(A, p, r ) x ← A[ r ] // x 为主元 i ← p - 1 for j ← p to r – 1 do if A[ j ] ≤ x then i ← i + 1 exchange A[i] ↔ A[j] exchange A[i + 1] ↔ A[r] return i + 1 p i j r x ≤ x > x unrestricted 2018/11/20 28

快速排序算法 i 和 j 如何改变： p i j r >x x ≤ x > x p i j r x ≤ x > x 當 j 那一格的數字比 x 還要大的時候， 我們直接將 j 移到下一格去，這樣仍舊符合我們前一頁定義的 i, j 特性 ≤ x > x Quicksort 29

快速排序算法 i 和 j 如何改变: p i j r ≤x x ≤ x > x p i j r x ≤ x > x 當 j 那格數字小於等於 x 的時候，我們將那個數字跟 i+1 那格的數字交換 然後 i 與 j 各往後移動一格 ≤ x > x Quicksort 30

范例: (Partition, x=A[r]=4) p,j p i j r r (a) (f) 2 8 7 1 3 5 6 4 2 1 3 8 7 5 6 4 p,i j p i j r r (b) (g) 2 8 7 1 3 5 6 4 2 1 3 8 7 5 6 4 p,i j p i (c) r r (h) 2 8 7 1 3 5 6 4 2 1 3 8 7 5 6 4 (d) p,i j p i r (i) r 黃色是pivot x, 灰色的部分是處理過的數字中大於 x 的數字 綠色的部分是處理過的數字中小於等於 x 的數字，白色的則是還沒處理到的數字。 2 8 7 1 3 5 6 4 2 1 3 4 7 5 6 8 p i j r (e) 2 1 7 8 3 5 6 4 Quicksort

快速排序算法 最坏情况：(n2) (对已排序好的輸入) T(n) = = 2018/11/20 32

快速排序算法 T(n)=(n2) (n2) n n-1 n-2 n-3 1 2 3 33 由於數字已經排序好，所以每次partition都只會把pivot切開 造成每次partition都很不平均的情況發生 33

快速排序算法 最佳情况划分： O(nlgn) 此时得到的两个子问题的大小都不可能大于n/2, 运行时间的递归表达式为： T(n) ≤ 2 T( n/2 ) + ( n ) 根据主定理，该递归式的解为： T(n) = O( nlgn ) 如果以固定比例进行划分，即使该比例很不平衡（如100:1），则其运行时间仍然为O( nlgn )。

快速排序算法 平均情况划分： (n lg n) 假设所有元素都不相同，则T(n)=O(n+X)，X 是 Partition 中第四行的执行次数。 每次调用 Partition 的時候，如果 A[i]<x<A[j] 或 A[j]<x<A[i]，A[i] 和 A[j] 将来就不会再相互比较.

快速排序算法 范例: 令 A={3，9，2，7，5}。 第一个回合之后，A={3，2，5，9，7}。 之后{3，2} 再也不会和 {9，7} 比较了。 将 A 的元素重新命名为 z1，z2，...，zn，其中 zi 是第 i 小的元素。且定义 Zij={zi，zi+1，...，zj}为zi与zj之间的元素集合。 定义zi : zj ：当且仅当第一个从 Zij 选出來的 pivot 是 zi 或 zj。

快速排序算法 对于任意的 i 和 j，發生 zi : zj 的概率为2/(j-i+1)， 因此，

快速排序算法 lg n … n 1 Total:Θ(n lg n) Quicksort 38 由於recursion tree的高度為log(n)， 每一層所花的時間為Θ(n) 因此最後的時間是Θ(n log n) Quicksort 38

快速排序算法 n … ≤n 1 Total:Θ(n lg n) 39 就算partition的時候沒有像上一頁切得很平均 只要能將一個長度為 n 的數列切成兩份長度比例為 1：9 (甚至 1:1000, 1:10000都可) 的話，時間仍舊是Θ(n log n) 39

快速排序算法 其他分析 E(n) = = 为了简单起见，假设： nE(n) = ------(1) E(n)為Average Case下的執行時間 q 是 partition 成兩部分的其中一部份長度 (1/n) * { E(q-1) + E(n-q) } for all q = 1 to n 則表示Partition之後平均情況下的執行時間 (用 n-1 替换掉 (1) 裡面的 n) 40

快速排序算法 41

快速排序的随机化版本 如何防止出现最坏情况发生？ 策略1：显示地对输入进行排列使得快速排序算法随机化 可以达到目的，是否还有其它策略呢？ RANDOMIZED-QUICKSORT(A, p, r ) if p < r RANDOMIZE-IN-PLACE(A) QUICKSORT( A ) 2018/11/20 42

快速排序的随机化版本 策略2：采用随机取样（random sampling）的随机化技术 做法：从子数组A[p…r]中随机选择一个元素作为主元，从而达到可以对输入数组的划分能够比较对称。 新排序算法调用RANDOMIZED-PARTITION RANDOMIZED-PARTITION(A, p, r ) i ← RANDOM( p, r ) exchange A[r] ↔ A[i] return PARTITION( A, p, r ) RANDOMIZED-QUICKSORT(A, p, r ) if p < r then q ← RANDOMIZED-PARTITION(A, p, r ) RANDOMIZED-QUICKSORT( A, p, q-1 ) RANDOMIZED-QUICKSORT( A, q+1, r ) 2018/11/20 43

第六讲 排序 内容提要： 排序问题 堆排序算法 快速排序算法 线性时间排序 排序算法比较 2018/11/20 44

排序算法时间的下界 本节探讨排序所耗用的时间复杂度下限。 比较排序：排序结果中，各元素的次序基于输入元素间的比较，这类算法成为比较排序。 任何比较排序算法，排序n个元素时至少耗用Ω(nlgn)次比较，其时间复杂度至少为Ω(nlgn) 合并排序和堆排序是渐近最优的 但不使用比较为基础的排序算法，在某些情形下可以在O(n)的时间内执行完毕。

排序算法时间的下界 一个以元素比较为基础的排序算法可以按照比较的顺序建出一个决策树（Decision-Tree）。 决策树是一棵满二叉树，表示某排序算法作用于给定输入所做的所有比较，忽略控制结构、数据移动等。

决策树模型： 每个内结点注明i : j (1≤i, j≤n),每个叶结点注明排列 排序算法的执行对应于遍历一条从树的根到叶节点的路径。 在每个内结点处做比较 ,内结点的左子树决定着 以后的比较，而右子树决定着 以后的比较 到达一个叶结点时，排序算法就已确定了顺序 每一个从根节点到叶子结点的路径对应于比较排序算法的一次实际执行过程。 排序算法正确工作的必要条件：n个元素的 中排列都要作为决策树的一个叶子。

排序算法时间的下界 1:2 2:3 1:3 <1,2,3> <1,3,2> <3,1,2> <2,1,3> <2,3,1> <3,2,1> ≤ > Eg. (a1 , a2 , a3) (9 , 2 , 6)

排序算法时间的下界 任何一个以元素比较为基础排序n个元素的排序算法，所对应的决策树的高度至少有Ω(nlogn)。 证明：因为可能有n!种可能的排序结果，故对应的Decision tree至少有n!个叶子结点。而高度为h的二叉树最多有 个叶子结点。因此h≥log(n!) ≥ Θ(nlogn)。(后者由斯特林公式(3.18)得证) 比较排序算法的最坏情况比较次数与其决策树的高度相等 定理1 任意比较排序算法在最坏情况下，都需要做Ω(nlogn)次比较。 堆排序和合并排序是渐近最优的排序算法 （因为它们的运行时间上界O(nlogn)与 定理1给出的最坏情况下界Ω(nlogn)一致。） 快速排序不是渐近最优的比较排序算法。但是，快速排序其执行效率平均而言较堆排序和合并排序还好。

计数排序 Counting Sort (计数排序) 不需要藉由比较來做排序。但是，必须依赖于一些对于待排序集合中元素性质的假设： 如果所有待排序元素均为整数，介于1到k之间。则当k=O(n), 时间复杂度：O(n+k) 基本思想：对每一个输入元素x，统计出小于x的元素的个数。然后，根据这一信息直接把元素x放到它在最终输出数组中的位置上。 在计数排序算法的代码中，需三个数组： 输入数组A[1…n] 存放排序结果的数组B[1…n] 提供临时存储区的数组C[0…k]

计数排序

计数排序

计数排序 排序算法是稳定的：具有相同值的元素在输出数组中的相对次序 与它们在输入数组中的次序 相同。 经常被当做基数排序算法的一个子过程 。

基数排序（Radix Sort） Radix Sort(基数排序)：假设所有待排序元素均为整数，至多d位。先按最低有效位进行排序，再按次低有效位排序，重复这个过程，直到对所有的d位数字都进行了排序。 基数排序关键是按位排序要稳定。 算法 Radix-Sort(A,d) { for i = 1 to d do use stable sort to sort A on digit i }

基数排序 最后排百位数 先排个位数 再排十位数 329 457 657 839 436 720 355 720 355 436 457

基数排序 Radix-Sort(A,d) { for i = 1 to d do use stable sort to sort A on digit i } 此处必须使用的稳定的排序算法，如果使用Counting Sort則每次迭代只需花Θ(n+k)的时间（假设每位数可以取k种可能的值）。 因此总共花费O(d(n+k))的时间。 如果d是常数，k=O(n)，则基数排序是一个可以在线性时间完成的排序算法。

基数排序 引理8.3：给定n个d位数，每一个数位可以取k种可能的值。基数排序算法能以Ө(d(n+k))的时间正确地对这些数进行排序。 引理8.4： 给定n个b位数和任何正整数r≤b, RADIX-SORT能在 时间内正确地对这些数进行排序。 对于给定的n值和b值，我们希望所选择的r值能够最小化表达式(b/r)(n+2r)。如果b< ，选择r=b, 此时为Ө(n)；如果b≥ ， 选择r= ，此时Ө(bn/lgn)

桶排序（Bucket Sort） 当元素均匀分布在某个区间时，Bucket sort平均能在O(n)的时间完成排序。 桶排序假设输入由一个随机过程产生，该过程将元素均匀的分布在区间[0，1)上。 基本思想： 把区间[0,1)划分成n个相同大小的子区间（称为桶）。 将n个输入数分布到各个桶中去。 先对各桶中元素进行排序，然后依次把各桶中的元素列出来即可。

桶排序

桶排序 假定要排序的n个元素A[1..n]均是介于[0,1]之間的数值，桶排序步骤如下： 1）准备n个桶(bucket)，B[1..n]，将元素x依照x所在的区间放进对应的桶中：即第 个桶 。 2）元素放进桶时，使用链表来存储，并利用插入排序法排序。 3）只要依序将链表串接起來，即得到已排序的n个元素。

桶排序

桶排序 时间复杂度分析：

第六讲 排序 内容提要： 排序问题 堆排序算法 快速排序算法 线性时间排序 排序算法比较 2018/11/20 63

二分法插入排序 特点：在直接插入排序的基础上减少比较的次数，即在插入Ri时改用二分法比较找插入位置，便得到二分法插入排序 限制：必须采用顺序存储方式。

二分法插入排序

二分法插入排序

二分法插入排序 比较次数：

二分法插入排序 性能分析:

二分法插入排序 结论：

表插入排序

表插入排序 记录的数据结构：

表插入排序 算法性能分析：

冒泡排序

冒泡排序

冒泡排序 算法评价：

冒泡排序 算法评价：

各种排序算法评价 排序算法之间的比较主要考虑以下几个方面∶ 算法的时间复杂度 算法的辅助空间 排序的稳定性 算法结构的复杂性 参加排序的数据的规模 排序码的初始状态

各种排序算法评价 当数据规模n较小时，n2和nlog2n的差别不大，则采用简单的排序方法比较合适 如直接插入排序或直接选择排序等 由于直接插入排序法所需记录的移动较多，当对空间的要求不多时，可以采用表插入排序法减少记录的移动 当文件的初态已基本有序时，可选择简单的排序方法 如直接插入排序或起泡排序等

各种排序算法评价 当数据规模n较大时，应选用速度快的排序算法 快速排序法最快，被认为是目前基于比较的排序方法中最好的方法 当待排序的记录是随机分布时，快速排序的平均时间最短。但快速排序有可能出现最坏情况，则快速排序算法的时间复杂度为O(n2)，且递归深度为n，即所需栈空间为O(n)

作业： 6.1-7 6.4-1 6.4-3 6.5-7 7.1-3 7.2-5 8.3-4 8.4-1 8.4-3