PowerPoint 演示文稿

Size: px

Start display at page:

Download "PowerPoint 演示文稿"

懿洪
5 years ago
Views:

1 算法基础主讲人 : 庄连生 { lszhuag@ustc.edu.c } Sprig 2010,USTC

2 第六讲排序内容提要 : 排序问题堆排序算法快速排序算法线性时间排序排序算法比较

3 第六讲排序内容提要 : 排序问题堆排序算法快速排序算法线性时间排序排序算法比较

4 排序问题问题描述 : 输入 : 个数的序列 a 1, a2,..., 输出 : 输入序列的一个重排 a a ' ', a 2,..., a 1 ', 使得 a a a ' ' ' 1 2 输入数据的结构可以各种各样, 比如元数组链表等 ; 排序问题是计算机科学领域中的最基本问题 : 1 应用广泛, 是许多算法的关键步骤 ; 2 已有很多成熟算法 ; 3 可以证明其非平凡下界, 是渐进最优的 ; 4 在实现过程中经常伴随着许多工程问题出现

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

6 第六讲排序内容提要 : 排序问题堆排序算法快速排序算法线性时间排序排序算法比较

7 二叉树二叉树 : 1 完全二叉树 : 深度为 k, 有个结点的二叉树当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 至的结点一一对应时, 称为完全二叉树特点 : 叶子结点只可能在层次最大的两层上出现 ; 对任一结点, 若其右分支下子孙的最大层次为 l, 则其左分支下子孙的最大层次必为 l 或 l+1 2 满二叉树 : 一棵深度为 k, 且有 ( 2^k-1 ) 个节点的二叉树特点 : 每一层上的结点数都是最大结点数 3 关系 : 满二叉树必然是完全二叉树, 反之不成立 ;

8 堆数据结构堆数据结构是一种数组对象, 可以被视为一棵完全二叉树树中每个节点与数组中存放该结点值的那个元素对应表示堆的数组对象 A 具有两个性质 : 1 legth[a]: 是数组中的元素个数 ; 2 heap-size[a]: 是存放在 A 中的堆得元素个数 ; 3 heap-size[a] legth[a]

9 堆数据结构作为数组对象的堆, 给定某个结点的下标 i, 则 : 1 父节点 PARENT( i ) = floor( i /2 ), 2 左儿子为 LEFT( i ) = 2 * i, 3 右儿子为 RIGHT( i ) = 2 * i + 1; 堆的分类 : 1 大根堆 : 除根节点之外的每个节点 i, 有 2 小根堆 : 除根节点之外的每个节点 i, 有 A[ PARENT ( i)] A[ i] A[ PARENT ( i)] A[ i] 在堆排序算法中, 我们使用大根堆, 堆中最大元素位于树根 ;

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

11 保持堆性质 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 ); 3if l heap-size[a] ad A[ l ] > A[ i ] 4 the largest l 5 else largest i 6if r heap-size[ A] ad A[ r ] > A[ largest ] 7 the largest r 8if largest I 9 the exchage A[ i ] A[ largest ] 10 MAX-HEAPIFY( A, largest )

12 保持堆性质 i i i

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

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

15 建堆操作输入是一个无序数组 A,BUILD-MAX-HEAP 把数组 A 变成一个最大堆, 伪代码如下 : BUILD-MAX-HEAP ( A ) 1 heap-size[a] legth[a]; 2for i FLOOR( legth[a]/2 ) dowto 1 3 do MAX-HEAPIFY( A, i ) 基本思想 : 数组 A[ (/2 +1) ] 中的元素都是树中的叶子结点, 因此每个都可以看作是只含一个元素的堆 BUILD-MAX-HEAP 对数组中每一个其它内结点从后往前都调用一次 MAX-HEAPIFY

16 建堆操作

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

18 堆排序算法基本思想 : 1 调用 BUILD-MAX-HEAP 将输入数组 A[1 ] 构建成一个最大堆 ; 2 互置 A[1] 和 A[] 位置, 使得堆的最大值位于数组正确位置 ; 3 减小堆的规模 ; 4 重新调整堆, 保持最大堆性质 HEAPSORT( A ) 1 BUILD-MAX-HEAP(A) 2 for i legth[a] dowto 2 3 do exchage A[1] A[] 4 heap-size[a] heap-size[a] -1 5 MAX-HEAPIFY( A, i )

19 堆排序算法

20 堆排序算法时间复杂度分析 : 调用 BUILD-MAX-HEAP 时间为 O(), -1 次 MAX-HAPIFY 调用的每一次时间代价为 O(lg) HEAPSORT 过程的总时间代价为 :O(lg) 思考 : 堆排序算法与插入排序算法设计策略关系是否类似? ( 减治法 )

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

22 优先级队列 HEAP-MAXIMUN HEAP-MAXIMUM( A ) 1 retur A[1] HEAP-EXTRACT-MAX, 运行时间为 O(lg) HEAP-EXTRACT-MAX( A ) 1if heap-size[a] < 1 2 the error heap uderflow 3max A[1] 4A[1] A[heap-size[A]] 5heap-size[A] heap-size[a] 1; 6MAX-HEAPIFY( A, 1 ) 7retur max

23 优先级队列 HEAP-INCREASE-KEY: 运行时间为 O(lg) HEAP-INCREASE-KEY(A, i, key ) 1if key < A[i] 2 the error ew key is smaller tha curret key 3A[ i ] key 4while i > 1 ad A[PARANT(i)] < A[i] 5 do exchage A[i ] A[PARANT(i)] 6 i PARANT(i) MAX-HEAP-INSERT: 运行时间为 O(lg) MAX-HEAP-INSERT(A, key ) 1heap-size[A] heap-size[a] + 1 2A[heap-size[A]] - 3HEAP-INCREASE-KEY( A, heap-size[a], key )

24 第六讲排序内容提要 : 排序问题堆排序算法快速排序算法线性时间排序排序算法比较

25 快速排序算法快速排序是 C.R.A.Hoare 于 1962 年提出的一种地排序算法对于包含个数的输入数组, 最坏情况运行时间为 Ө( 2 ), 期望运行时间为 Ө(lg) 且常数因子较小基本思想是采用了一种分治的策略把未排序数组分为两部分, 然后分别递归调用自身进行排序 : 1 分解 : 数组 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] q x A[q+1..r] 2 解决 : 递归调用快速排序, 对子数组 A[p...q-1] 和 A[q+1..r] 排序 ; 3 合并 : 不需要任何操作

26 快速排序算法快速排序伪代码 : QUICKSORT(A, p, r ) 1if p < r 2 the q PARTITION(A, p, r ) 3 QUICKSORT( A, p, q-1 ) 4 QUICKSORT( A, q+1, r ) * 为排序一个完整数组, 最初调用 QUICKSORT(A, 1, legth[a]) 数组划分过程 PARTITION 是 QUICKSORT 算法的关键, 它对子数组 A[p..r] 进行就地排序

27 快速排序算法数组划分过程 PARTITION PARTITION(A, p, r ) 1x A[ r ] // x 为主元 2i p - 1 3for j p to r 1 4 do if A[ j ] x 5 the i i exchage A[i] A[j] 7exchage A[i + 1] A[r] 8retur i + 1 p i j r x x > x urestricted

28 快速排序算法 i 和 j 如何改变 : p i j r >x x x > x p i j r x x > x Quicksort 28

29 快速排序算法 i 和 j 如何改变 : p i j r x x x > x p i j r x x > x Quicksort 29

30 范例 : (Partitio, x=a[r]=4) (a) i p,j r (f) p i j r (b) p,i j r (g) p i j r (c) p,i j r (h) p i r (d) p,i j r (i) p i r (e) p i j r Quicksort

31 快速排序算法最坏情况 : ( 2 ) ( 對於已排序好的輸入 ) T() = = max{ T ( q 1 q 1) T ( q)} ( ) max { T( k) T( k 1)} ( ) 0 k

32 快速排序算法 T()= ( 2 ) ( 2 ) 32

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

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

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

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

37 快速排序算法 lg Total:Θ( lg ) Quicksort 37

38 快速排序算法 log log Total:Θ( lg ) 38

39 39 其他分析 E() = = 为了简单起见, 假设 : E() = E() = (1) (-1)E(-1) = (2) q q E q E 1 )} ( 1) ( { 1 1) ( 1 1 ) ( 2 1) ( k k E 1 1 ) ( 2 1 k k E ) ( 2 k k E ) ( 2 1) ( 1) ( k k E ( 用 -1 替换掉 (1) 裡面的 ) 快速排序算法

40 快速排序算法 40

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

42 快速排序的随机化版本策略 2: 采用随机取样 (radom samplig) 的随机化技术做法 : 从子数组 A[p r] 中随机选择一个元素作为主元, 从而达到可以对输入数组的划分能够比较对称 RANDOMIZED-PARTITION(A, p, r ) 1 i RANDOM( p, r ) 2 exchage A[r] A[i] 3 retur PARTITION( A, p, r ) 新排序算法调用 RANDOMIZED-PARTITION RANDOMIZED-QUICKSORT(A, p, r ) 1if p < r 2 the q RANDOMIZED-PARTITION(A, p, r ) 3 QUICKSORT( A, p, q-1 ) 4 QUICKSORT( A, q+1, r )

43 第六讲排序内容提要 : 排序问题堆排序算法快速排序算法线性时间排序排序算法比较

44 排序算法时间的下界本节探讨排序所耗用的时间复杂度下限任何一个以比较为基础的排序算法, 排序个元素时至少耗用 Ω(lg) 次比较, 其时间复杂度至少为 Ω(lg); 但不使用比较为基础的排序算法, 在某些情形下可以在 O() 的时间内执行完毕

45 排序算法时间的下界一个以元素比较为基础的排序算法可以按照比较的顺序建出一个决策树 (Decisio-Tree) 决策树模型 : 1 每一个从根节点到叶子结点的路径都代表一种排序结果 2 任何一个以元素比较为基础排序个元素的排序算法, 所对应的决策树的高度至少有 Ω(log)

46 排序算法时间的下界 a 1 :a 2 > Eg. (a 1 a 2 a 3 ) (9 2 6) a 2 :a 3 a 1 :a 3 > > <1,2,3> a 1 :a 3 <2,1,3> a 2 :a 3 > > <1,3,2> <3,1,2> <2,3,1> <3,2,1>

47 排序算法时间的下界

48 计数排序

49 计数排序

50 计数排序

51 计数排序排序算法是稳定的, 经常被当做基数排序算法的一个子过程

52 基数排序 (Radix Sort)

53 基数排序

54 基数排序

55 基数排序

56 桶排序 (Bucket Sort)

57 桶排序

58 桶排序

59 桶排序

60 桶排序时间复杂度分析 :

61 第六讲排序内容提要 : 排序问题堆排序算法快速排序算法线性时间排序排序算法比较

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

63 二分法插入排序

64 二分法插入排序

65 二分法插入排序比较次数 :

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

67 二分法插入排序结论 :

68 表插入排序

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

70 表插入排序算法性能分析 :

71 冒泡排序

72 冒泡排序

73 冒泡排序算法评价 :

74 冒泡排序算法评价 :

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

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

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

78 谢谢! Q & A

算法分析与问题的计算复杂度

算法分析与问题的计算复杂度王子辰 2016.5.20 概要第一部分检索算法的评价指标平凡下界决策树与时间复杂度第二部分排序冒泡排序堆排序等排序算法排序算法的复杂度下界第三部分选择选择问题的时间复杂度分析问题之间的归约性概要第一部分检索算法的评价指标平凡下界决策树与时间复杂度第二部分排序冒泡排序堆排序等排序算法排序算法的复杂度下界第三部分选择选择问题的时间复杂度分析