PowerPoint 演示文稿

Size: px

Start display at page:

Download "PowerPoint 演示文稿"

刑饲乔
4 years ago
Views:

数据结构与算法 ( 八 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008.

1 数据结构与算法 ( 八 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社, ( 十一五国家级规划教材 )

2 第八章内排序大纲 8.1 排序问题的基本概念 8.2 插入排序 ( Shell 排序 ) 8.3 选择排序 ( 堆排序 ) 8.4 交换排序冒泡排序快速排序 8.5 归并排序 8.6 分配排序和索引排序 8.7 排序算法的时间代价内排序知识点总结 2

3 8.1 基本概念 8.1 基本概念序列 (Sequence): 线性表由记录组成记录 (Record): 结点, 进行排序的基本单位关键码 (Key): 唯一确定记录的一个或多个域排序码 (Sort Key): 作为排序运算依据的一个或多个域 3

4 8.1 基本概念什么是排序? 排序将序列中的记录按照排序码顺序排列起来排序码域的值具有不减 ( 或不增 ) 的顺序内排序整个排序过程在内存中完成 4

5 8.1 基本概念排序问题给定一个序列 R = { r 1, r 2,,r n } 其排序码分别为 k = { k 1, k 2,,k n } 排序的目的 : 将记录按排序码重排形成新的有序序列 R = { r 1, r 2,,r n } 相应排序码为 k = { k 1, k 2,,k n } 排序码的顺序其中 k 1 k 2 k n, 称为不减序或 k 1 k 2 k n, 称为不增序 5

6 8.1 基本概念正序 vs. 逆序正序序列 : 待排序序列正好符合排序要求逆序序列 : 把待排序序列逆转过来, 正好符合排序要求例如, 要求不升序列正序! 逆序! 6

7 8.1 基本概念排序的稳定性稳定性存在多个具有相同排序码的记录排序后这些记录的相对次序保持不变例如, 稳定性的证明形式化证明稳定! 7

8 8.1 基本概念排序的稳定性稳定性存在多个具有相同排序码的记录排序后这些记录的相对次序保持不变例如, 不稳定性的证明反例说明不稳定! 8

9 排序算法的衡量标准时间代价 : 记录的比较和移动次数空间代价 8.1 基本概念算法本身的繁杂程度

10 第八章内排序思考 1. 排序算法的稳定性有何意义? 2. 为何需要考虑正序与逆序序列? 10

11 大纲 8.1 排序问题的基本概念 8.2 插入排序 ( Shell 排序 ) 8.3 选择排序 ( 堆排序 ) 8.4 交换排序冒泡排序快速排序 8.5 归并排序 8.6 分配排序和索引排序 8.7 排序算法的时间代价内排序知识点总结 11

12 8.2 插入排序 8.2 插入排序直接插入排序 Shell 排序 12

13 8.2 插入排序插入排序动画

14 8.2 插入排序插入排序算法 template <class Record> void ImprovedInsertSort (Record Array[], int n){ //Array[] 为待排序数组,n 为数组长度 Record TempRecord; // 临时变量 for (int i=1; i<n; i++){ // 依次插入第 i 个记录 TempRecord = Array[i]; // 从 i 开始往前寻找记录 i 的正确位置 int j = i-1; // 将那些大于等于记录 i 的记录后移 while ((j>=0) && (TempRecord < Array[j])){ Array[j+1] = Array[j]; j = j - 1; } // 此时 j 后面就是记录 i 的正确位置, 回填 Array[j+1] = TempRecord; } }

15 8.2 插入排序算法分析稳定空间代价 :Θ(1) 时间代价 : 最佳情况 :n-1 次比较,2(n-1) 次移动,Θ(n) 最差情况 : Θ(n 2 ) 比较次数为移动次数为平均情况 :Θ(n 2 ) n 1 i 1 n 1 i 1 i n n n 2 ( 1) / 2 ( ) 2 ( i 2) ( n 1)( n 4) / 2 ( n ) 15

16 8.2.2 Shell 排序 Shell 排序直接插入排序的两个性质 : 在最好情况 ( 序列本身已是有序的 ) 下时间代价为 Θ(n) 对于短序列, 直接插入排序比较有效 Shell 排序有效地利用了直接插入排序的这两个性质 16

17 8.2.2 Shell 排序 Shell 排序算法思想先将序列转化为若干小序列, 在这些小序列内进行插入排序逐渐增加小序列的规模, 而减少小序列个数, 使得待排序序列逐渐处于更有序的状态最后对整个序列进行扫尾直接插入排序, 从而完成排序 17

18 8.2.2 Shell 排序 Shell 排序动画

19 增量每次除以 2 递减的 Shell 排序 template <class Record> void ShellSort(Record Array[], int n) { // Shell 排序,Array[] 为待排序数组,n 为数组长度 int i, delta; // 增量 delta 每次除以 2 递减 for (delta = n/2; delta>0; delta /= 2) for (i = 0; i < delta; i++) // 分别对 delta 个子序列进行插入排序 // & 传 Array[i] 的地址, 数组总长度为 n-i ModInsSort(&Array[i], n-i, delta); // 如果增量序列不能保证最后一个 delta 间距为 1 // 可以安排下面这个扫尾性质的插入排序 // ModInsSort(Array, n, 1); }

20 8.2.2 Shell 排序针对增量而修改的插入排序算法 template <class Record> // 参数 delta 表示当前的增量 void ModInsSort(Record Array[], int n, int delta) { int i, j; // 对子序列中第 i 个记录, 寻找合适的插入位置 for (i = delta; i < n; i += delta) // j 以 dealta 为步长向前寻找逆置对进行调整 for (j = i; j >= delta; j -= delta) { if (Array[j] < Array[j-delta]) // 逆置对 swap(array, j, j-delta);// 交换 else break; } } 20

21 8.2.2 Shell 排序算法分析不稳定空间代价 :Θ(1) 时间代价增量每次除以 2 递减,Θ(n 2 ) 选择适当的增量序列可以使得时间代价接近 Θ(n) 21

22 8.2.2 Shell 排序 Shell 排序选择增量序列增量每次除以 2 递减效率仍然为 Θ(n 2 ) 问题 : 选取的增量之间并不互质间距为 2 k-1 的子序列, 都是由那些间距为 2 k 的子序列组成的上一轮循环中这些子序列都已经排过序了, 导致处理效率不高

23 8.2.2 Shell 排序 Hibbard 增量序列 Hibbard 增量序列 {2 k -1,2 k-1-1,,7,3,1} Shell(3) 和 Hibbard 增量序列的 Shell 排序的效率可以达到 Θ(n 3/2 ) 选取其他增量序列还可以更进一步减少时间代价 23

24 8.2.2 Shell 排序 Shell 最好的代价呈 2 p 3 q 形式的一系列整数 : 1, 2, 3, 4, 6, 8, 9, 12 Θ(n log 2 n) 24

25 8.2.2 Shell 排序思考 1. 插入排序的变种发现逆序对直接交换查找待插入位置时, 采用二分法 2. Shell 排序中增量作用是什么? 增量为 2 和增量为 3 的序列, 哪个更好? 为什么? 3. Shell 排序的每一轮子序列排序可以用其他方法吗? 25

26 大纲 8.1 排序问题的基本概念 8.2 插入排序 ( Shell 排序 ) 8.3 选择排序 ( 堆排序 ) 8.4 交换排序冒泡排序快速排序 8.5 归并排序 8.6 分配排序和索引排序 8.7 排序算法的时间代价内排序知识点总结 26

27 8.3 选择排序 8.3 选择排序直接选择排序依次选出剩下的未排序记录中的最小记录堆排序堆排序 : 基于最大堆来实现 27

28 8.3 选择排序直接选择排序动画

29 8.3 选择排序直接选择排序 template <class Record> void SelectSort(Record Array[], int n) { // 依次选出第 i 小的记录, 即剩余记录中最小的那个 for (int i=0; i<n-1; i++) { // 首先假设记录 i 就是最小的 int Smallest = i; // 开始向后扫描所有剩余记录 for (int j=i+1;j<n; j++) // 如果发现更小的记录, 记录它的位置 if (Array[j] < Array[Smallest]) Smallest = j; // 将第 i 小的记录放在数组中第 i 个位置 swap(array, i, Smallest); } } 29

30 不稳定 8.3 选择排序直接选择排序性能分析空间代价 :Θ(1) 时间代价比较次数 :Θ(n 2 ) 交换次数 :n-1 总时间代价 :Θ(n 2 ) 30

31 8.3.2 堆排序堆排序选择类内排序直接选择排序 : 直接从剩余记录中线性查找最大记录堆排序 : 基于最大堆来实现, 效率更高选择类外排序置换选择排序赢者树败方树 31

32 8.3.2 堆排序最大堆排序过程示意图

33 8.3.2 堆排序最大堆排序过程示意图

34 8.3.2 堆排序堆排序算法 template <class Record> void sort(record Array[], int n){ int i; // 建堆 MaxHeap<Record> max_heap = MaxHeap<Record>(Array,n,n); // 算法操作 n-1 次, 最小元素不需要出堆 for (i = 0; i < n-1; i++) // 依次找出剩余记录中的最大记录, 即堆顶 max_heap. RemoveMax(); } 34

35 8.3.2 堆排序算法分析建堆 :Θ(n) 删除堆顶 : Θ(log n ) 一次建堆,n 次删除堆顶总时间代价为 Θ(nlog n) 空间代价为 Θ(1) 35

36 思考直接选择排序为什么不稳定? 怎么修改一下让它变稳定改写堆排序算法, 发现逆序对直接交换 36

37 大纲 8.1 排序问题的基本概念 8.2 插入排序 (Shell 排序 ) 8.3 选择排序 ( 堆排序 ) 8.4 交换排序冒泡排序快速排序 8.5 归并排序 8.6 分配排序和索引排序 8.7 排序算法的时间代价内排序知识点总结 37

38 8.4 交换排序冒泡排序快速排序 38

39 8.4.1 冒泡排序冒泡排序算法思想不停地比较相邻的记录, 如果不满足排序要求, 就交换相邻记录, 直到所有的记录都已经排好序检查每次冒泡过程中是否发生过交换, 如果没有, 则表明整个数组已经排好序了, 排序结束避免不必要的比较冒泡排序之舞 39

40 8.4.1 冒泡排序冒泡排序动画

41 8.4.1 冒泡排序冒泡排序算法 template <class Record> void BubbleSort(Record Array[], int n) { bool NoSwap; // 是否发生了交换的标志 int i, j; for (i = 0; i < n-1; i++) { NoSwap = true; // 标志初始为真 for (j = n-1; j > i; j--){ if (Array[j] < Array[j-1]) { // 判断是否逆置 swap(array, j, j-1); // 交换逆置对 NoSwap = false // 发生了交换, 标志变为假 } if (NoSwap) // 没发生交换, 则已完成排好序 return; } } } 41

42 8.4.1 冒泡排序算法分析稳定空间代价 :Θ(1) 时间代价分析比较次数最少 :Θ(n) 最多 : n 1 2 ( n i) n( n 1) / 2 ( n ) 交换次数最多为 i 1 Θ(n 2 ), 最少为 0, 平均为 Θ(n 2 ) 时间代价结论最大, 平均时间代价均为 Θ(n 2 ) 最小时间代价为 Θ(n): 最佳情况下只运行第一轮循环 42

43 8.4.2 快速排序快速排序算法思想选择轴值 (pivot) 将序列划分为两个子序列 L 和 R, 使得 L 中所有记录都小于或等于轴值,R 中记录都大于轴值对子序列 L 和 R 递归进行快速排序 20 世纪十大算法 Top 10 Algorithms of the Century London 的 Elliot Brothers Ltd 的 Tony Hoare 提出的快速排序基于分治法的排序 : 快速归并 43

44 分治策略的实例快速排序分治策略的基本思想 BST 查找插入删除算法快速排序归并排序二分检索主要思想划分求解子问题 ( 子问题不重叠 ) 综合解 44

45 8.4.2 快速排序快速排序分治思想最终排序结果 :

46 8.4.2 快速排序轴值选择尽可能使 L, R 长度相等选择策略 : 选择最左边记录随机选择选择平均值 46

47 8.4.2 快速排序一次分割过程 i 选择轴值并存储轴值最后一个元素放到轴值位置初始化下标 i, j, 分别指向头尾 i 递增直到遇到比轴值大的元素, 将此元素覆盖到 j 的位置 ;j 递减直到遇到比轴值小的元素, 将此元素覆盖到 i 的位置重复上一步直到 i==j, 将轴值放到 i 的位置, 完毕 47 j

48 8.4.2 快速排序快速排序算法 template <class Record> void QuickSort(Record Array[], int left, int right) { // Array[] 为待排序数组,left,right 分别为数组两端 if (right <= left) // 只有 0 或 1 个记录, 就不需排序 return; int pivot = SelectPivot(left, right); // 选择轴值 swap(array, pivot, right); // 轴值放到数组末端 pivot = Partition(Array, left, right); // 分割后轴值正确 QuickSort(Array, left, pivot-1); // 右子序列递归快排 QuickSort(Array, pivot +1, right); } int SelectPivot(int left, int right) { } // 右子序列递归快排 // 选择轴值, 参数 left,right 分别表示序列的左右端下标 return (left+right)/2; // 选中间记录作为轴值 48

49 8.4.2 快速排序分割函数 template <class Record> int Partition(Record Array[], int left, int right) { // 分割函数, 分割后轴值已到达正确位置 int l = left; // l 为左指针 int r = right; // r 为右指针 Record TempRecord = Array[r]; // 保存轴值 while (l!= r) { // l, r 不断向中间移动, 直到相遇 // l 指针向右移动, 直到找到一个大于轴值的记录 while (Array[l] <= TempRecord && r > l) l++; if (l < r) { } // 未相遇, 将逆置元素换到右边空位 Array[r] = Array[l]; r--; // r 指针向左移动一步 49

50 8.4.2 快速排序 } // r 指针向左移动, 直到找到一个大于轴值的记录 while (Array[r] >= TempRecord && r > l) r--; if (l < r) { Array[l] = Array[r]; l++; } } //end while // 未相遇, 将逆置元素换到左空位 // l 指针向右移动一步 Array[l] = TempRecord; // 把轴值回填到分界位置 l 上 return l; // 返回分界位置 l 50

51 8.4.2 快速排序时间代价长度为 n 的序列, 时间为 T(n) T(0) = T(1) =1 选择轴值时间为常数分割时间为 cn 分割后长度分别为 i 和 n-i-1 左右子序列 T(i) 和 T(n-i-1) 求解递推方程 T ( n) T ( i) T ( n 1 i) cn 51

52 8.4.2 快速排序最差情况总的时间代价为 : T( n) T( n 1) cn T( n 1) T( n 2) c( n 1) T( n 2) T( n 3) c( n 2) M T(2) T(1) c(2) n 2 ( ) (1) ( ) T n T c i n i 2 52

53 8.4.2 快速排序 T ( n) 2 T ( n / 2) cn 最佳情况 T ( n) T ( n / 2) c n n/2 T ( n / 2) T ( n / 4) c n/ 2 n/ 4 T ( n / 4) T ( n /8) c n/ 4 n/8 M T(2) T(1) 2 1 c T( n) T(1) clog n n 1 T( n) cn log n n ( nlog n) 53

54 8.4.2 快速排序等概率情况也就是说, 轴值将数组分成长度为 0 和 n-1, 1 和 n-2, 的子序列的概率是相等的, 都为 1/n T(i) 和 T(n-1-i) 的平均值均为 n 1 1 T( i) T ( n 1 i) T ( k) n n 1 k 0 n T( n) cn ( T( k) T( n 1 k)) cn T( k) n n k 0 k 0 nt ( n) ( n 1) T ( n 1) 2cn c T ( n) ( nlog n) 54

55 8.4.2 快速排序快速排序算法分析最差情况 : 时间代价 :Θ(n 2 ) 空间代价 :Θ(n) 最佳情况 : 时间代价 :Θ(nlog n) 空间代价 :Θ(log n) 平均情况 : 时间代价 :Θ(nlog n) 空间代价 :Θ(log n) 55

56 8.4.2 快速排序思考冒泡排序和直接选择排序哪个更优快速排序为什么不稳定快速排序可能的优化轴值选择 RQS 小子串不递归 ( 阈值 28? ) 消除递归 ( 用栈, 队列?) 56

57 大纲 8.1 排序问题的基本概念 8.2 插入排序 (Shell 排序 ) 8.3 选择排序 ( 堆排序 ) 8.4 交换排序冒泡排序快速排序 8.5 归并排序 8.6 分配排序和索引排序 8.7 排序算法的时间代价内排序知识点总结 57

58 8.5 归并排序归并排序思想划分为两个子序列分别对每个子序列归并排序有序子序列合并先划分再归并 ( ) ( )( ) (25 34)(45 32)(78 12)(34 64) (25)(34)(45)(32)(78)(12)(34 )(64) (25 34)(32 45)(12 78)(34 64) ( )( ) ( ) 58

59 8.5 归并排序两路归并排序 template <class Record> void MergeSort(Record Array[], Record TempArray[], int left, int right) { // Array 为待排序数组,left,right 两端 int middle; if (left < right) { // 序列中只有 0 或 1 个记录, 不用排序 middle = (left + right) / 2; // 平分为两个子序列 // 对左边一半进行递归 MergeSort(Array,TempArray,left,middle); // 对右边一半进行递归 MergeSort(Array, TempArray,middle+1,right); Merge(Array, TempArray,left,right,middle); // 归并 } } 59

60 8.5 归并排序归并函数 // 两个有序子序列都从左向右扫描, 归并到新数组 template <class Record> void Merge(Record Array[], Record TempArray[], int left, int right, int middle) { int i, j, index1, index2; // 将数组暂存入临时数组 for (j = left; j <= right; j++) TempArray[j] = Array[j]; index1 = left; // 左边子序列的起始位置 index2 = middle+1; // 右边子序列的起始位置 i = left; // 从左开始归并 60

61 8.5 归并排序 while (index1 <= middle && index2 <= right) { // 取较小者插入合并数组中 if (TempArray[index1] <= TempArray[index2]) Array[i++] = TempArray[index1++]; else Array[i++] = TempArray[index2++]; } while (index1 <= middle) // 只剩左序列, 可以直接复制 Array[i++] = TempArray[index1++]; while (index2 <= right) // 与上个循环互斥, 复制右序列 Array[i++] = TempArray[index2++]; } 61

62 8.5 归并排序归并算法优化同优化的快速排序一样, 对基本已排序序列直接插入排序 R.Sedgewick 优化 : 归并时从两端开始处理, 向中间推进, 简化边界判断 62

63 8.5 归并排序 R.Sedgewick 优化归并思想 ( ) 先划分再归并 ( )( ) (25 34)(45 32)(78 12)(34 64) (25)(34)(45)(32)(78)(12)(34 )(64) (25 34)(45 32)(12 78)(64 34 ) ( )( ) ( ) 63

64 8.5 归并排序 k i1 i2 R.Sedgewick 优化归并 i2 64

65 8.5 归并排序优化的归并排序 ( 阈值 28) template <class Record> void ModMergeSort(Record Array[], Record TempArray[], int left, int right) { // Array 为待排序数组,left,right 两端 int middle; if (right-left+1 > THRESHOLD) {// 长序列递归 middle = (left + right) / 2; // 从中间划为两个子序列 ModMergeSort(Array, TempArray,left,middle); // 左 } ModMergeSort(Array, TempArray,middle+1,right);// 右 // 对相邻的有序序列进行归并 ModMerge(Array, TempArray,left,right,middle); } else InsertSort(&Array[left],right-left+1); // 归并 // 小序列插入排序 65

66 8.5 归并排序优化的归并函数 template <class Record> void ModMerge(Record Array[],Record TempArray[],int left,int right,int middle) { int index1,index2; // 两个子序列的起始位置 int i,j,k ; for (i = left; i <= middle; i++) TempArray[i] = Array[i]; // 复制左边的子序列 for (j = 1; j <= right-middle; j++)// 颠倒复制右序列 TempArray[right-j+1] = Array[j+middle]; for (index1=left, index2=right, k=left; k<=right; k++) if (TempArray[index1] <= TempArray[index2]) Array[k] = TempArray[index1++]; else Array[k] = TempArray[index2--]; } 66

67 8.5 归并排序算法复杂度分析空间代价 :Θ(n) 划分时间排序时间归并时间 T ( n) 2 T ( n / 2) cn T(1) = 1 归并排序总时间代价也为 Θ(nlog n) 不依赖于原始数组的输入情况, 最大最小以及平均时间代价均为 Θ(nlog n) 67

68 8.5 归并排序思考普通归并和 Sedgewick 算法都是稳定的吗? 两个归并算法哪个更优? 二者的比较次数和赋值次数归并时子序列下标是否需要边界判断 68

69 数据结构与算法谢谢聆听国家精品课数据结构与算法张铭, 王腾蛟, 赵海燕高等教育出版社, 十一五国家级规划教材

第 8 章内排序

第 8 章内排序引言排序和查找是数据结构的重要运算排序的分类内部排序 : 待排序记录数少放在内存, 排序过程在内存进行, 称为内部排序 (internal sorting) 外部排序 : 待排序记录数大, 内存无法容纳所有记录, 排序过程中还需要访问外存, 称为外部排序 (external sorting) 2 课程内容 8.1 基本概念 8.2 三种 O(n 2 ) 的简单排序 8.3 Shell