幻灯片 1

Size: px

Start display at page:

Download "幻灯片 1"

风驯於
7 years ago
Views:

1 第四章 : 排序和算法分析算法效率的度量讨论 : 1 什么是算法? 如何评判算法的好坏? 2 时间复杂度和空间复杂度如何表示? 3 计算举例 1

2 1 什么是算法? 如何评判一个算法的好坏? 算法 : 是对特定问题求解步骤的一种描述, 它是指令的有限序列, 是一系列输入转换为输出的计算步骤算法的基本特性 : 有穷性确定性可行性必有输出算法评价指标 : 好的程序设计 : 好算法 + 好结构正确性可读性健壮性高效率与低存储量需求 ( 见课本 P20) 常用时间复杂度来衡量常用空间复杂度来衡量 2

3 渐进符号 ( O ) 的定义 : 当且仅当存在一个正的常数 C, 使得对所有的 n n 0, 有 f ( n) Cg( n) 例 :, 则 : f ( n) = O( g( n) ) 3n+2=O(n) 因为 3n+2 4n for n 2 6*2 n +n 2 =O(2 n ) 因为 6*2 n +n 2 7*2 n for n 4 3

4 解 : 计算举例例 : 分析以下程序段的时间复杂度 i=1; while(i<=n) i=i*2; 1 2 该算法的运行时间由程序中所有语句的频度 ( 即该语句重复执行的次数 ) 之和构成算法的时间复杂度由嵌套最深层语句的频度决定分析 : 显然, 语句 1 的频度是 1 设语句 2 的频度是 f(n), 则有 : ( ) 2 f n n 即 f(n) log 2 n, 取最大值 f(n)=log 2 n 所以该程序段的时间复杂度 T(n)=1+f(n)=1+ log 2 n= O( log 2 n) 4

5 设算法的问题规模为 n ; 频度 : 语句重复执行的次数称为该语句的频度, 记 f(n) 对算法各基本操作的频度求和, 便可得算法的时间复杂度但实际中我们所关心的主要是一个算法所花时间的数量级, 即取算法各基本操作的最大频度数量级时间复杂度 : 算法执行时间度量, 记 T(n)=O( maxlevel(f(n)) ) f(n) = 1 + n + n 2 + n 3 T(n) = O( n 3 ) 5

6 例, X = X + 1 ; for ( i = 1 ; i<=n ; i++ ) X = X + 1 ; for ( i = 1 ; i<=n ; i++ ) for ( j = 1 ; j<=n ; j++ ) { X = X + 1 ; X = X + 1 ; } 算法执行总的时间花费为 1+n+2n 2 算法的时间复杂度为 T(n) = O(n 2 ) O(1), O(logn), O(n k ), O(2 n ) 6

7 有时, 算法中基本操作重复执行的次数随问题的输入不同而不同, 通常分析最坏情况下的时间复杂度例, 顺序查找算法 Status serch ( int a[ ], int n, int e ) { for ( i = 0 ; i <=n - 1 ; ++i ) if ( e == a[i] ) return TRUE ; } return FALSE ; 最好 1 次比较, 最坏 n 次比较, 平均 (n+1)/2 次比较 7

8 2 时间复杂度和空间复杂度如何表示? 时间复杂度 T(n) 按数量级递增顺序为 : 多项式阶复杂度低复杂度高注 : 1 ) O () 为渐近符号 2 ) 空间复杂度 S(n) 按数量级递增顺序也与上表类似 8

9 内部排序排序介绍排序 ( Sorti ng ) 是数据处理中一种很重要的运算, 同时也是很常用的运算, 一般数据处理工作 25% 的时间都在进行排序简单地说, 排序就是把一组记录 ( 元素 ) 按照某个域的值的递增 ( 即由小到大 ) 或递减 ( 即由大到小 ) 的次序重新排列的过程 9

10 排序的基本概念排序将一个包含若干数据元素 ( 或记录 ) 的任意序列, 重新排列成一个按关键字有序的序列的过程按待排序记录所在的位置, 可分为 : 内部排序 : 待排序记录存放在内存外部排序 : 当待排序记录数量很大时, 一部分记录需放在外存, 在排序过程中就需要对外存进行访问 10

11 内部排序分为 : 插入排序快速排序选择排序归并排序基数排序 ( 略过 ) 排序基本操作比较两个关键字大小将记录从一个位置移动到另一个位置 11

12 待排序记录在内存中怎样存储和处理? 1 顺序排序排序时直接移动记录 ; 2 链表排序排序时只移动指针 ; 3 地址排序排序时先移动地址, 最后再移动记录注 : 地址排序中可以增设一维数组来专门存放记录的地址按排序算法的时间复杂度不同, 可分为 3 类 : 简单的排序算法 : 时间效率低, O(n 2 ) 先进的排序算法 : 时间效率高, O( nlog 2 n ) 基数排序算法 : 时间效率高, O( d n) d = 关键字的位数 ( 长度 ) 12

13 1. 插入排序直接插入排序希尔排序 13

14 1.1 直接插入排序基本操作是 : 将一个记录插入到已排好序的有序表中, 从而得到一个新的记录数增 1 的有序表基本思想是 : 当插入第 i ( i 2) 个记录时, 前面的 r [1], r [2],, r [i - 1] 已经排好序这时, 将 r [i ] 的关键字依次与 r[i - 1], r[i - 2] 的关键字进行比较, 并同时将相关记录位置后移, 直到找到插入 r [i ] 的合适位置 14

15 例 1.1 有一组记录的关键字初始排列如下 : 请使用直接插入排序方法, 将以上记录按照关键字非递减排列 15

16 初始关键字 : (49) 结果 i=2: (38) (38 49) i=3: (65) ( ) i=4: (97) ( ) i=5: (76) ( ) i=6: (13) ( ) i=7: (27) ( ) 49 i=8: (49) ( ) 16

17 算法实现 void InsertSort(DataType a[], int n) /* 用直接插入法对 a[0]--a[n-1] 排序 */ { int i, j; DataType temp; for(i = 0; i < n-1; i++) { temp = a[i+1]; j = i; while(j > -1 && temp.key < a[j].key) { a[j+1] = a[j]; j--; } a[j+1] = temp; } } 17

18 链表实现算法 #include <stdio.h> typedef int KeyType; typedef struct {KeyType key; } DataType; void main(void) { DataType test[6]={64,5,7,89,6,24}; int i, n = 6; SeqList mylist; ListInitiate(&myList); #define MaxSize 100 #include "SeqList.h" for(i = 0; i < n; i++) ListInsert(&myList, i, test[i]); InsertSort(myList.list, mylist.size); for(i=0; i<n; i++) printf("%d ", mylist.list[i].key); } 18

19 1.1 直接插入排序的算法分析算法简便, 容易实现当待排序记录数 n 很小时, 是一种很好的排序方法当待排序记录数 n 很大时, 不宜使用时间复杂度为 O( n 2 ) 空间复杂度为 S( n) =O( 1), 即使用一个辅助单元 ( 第 0 个单元 ) 19

20 基本思想 : 1.2 希尔排序 1 ) 先取一个正整数 d1 ( d1 < 记录数 n ), 把所有相隔 d1 的记录放一组, 这样就把整个待排记录序列分割成若干个子序列, 对每个子序列进行直接插入排序 2 ) 再取 d2 < d1, 把所有相隔 d2 的记录放一组, 对每一组内的记录进行直接插入排序 3 ) 最后取 di = 1, 即把所有记录放在一组进行直接插入排序 20

21 1.2 希尔排序例题如下 : 对下列关键字进行希尔排序 : 取 d1 = 5, d2 = 3, d3 = 1 21

22 初始关键字 : 取 d1=5 一趟分组 : 一趟排序结果 :

23 取 d2=3 二趟分组 : 二趟排序结果 : 取 d3=1 三趟分组 : 三趟排序结果 :

24 1.2 希尔排序的特点子序列的构成不是简单的逐段分割, 而是将相隔某个增量的记录组成一个子序列关键字较小的记录跳跃式前移, 在进行最后一趟增量为 1 的插入排序时, 序列已基本有序设 n 为待排序记录个数, 一般 di 取值如下 : d1 = n/2, d2 直到 di = 1 = d1/2,, 24

25 2 交换排序交换排序的基本思想是 : 利用交换数据元素的位置进行排序的方法交换排序的主要算法有 : 1) 冒泡排序 2) 快速排序 25

26 2.1 冒泡排序 1 基本思路 : 每趟不断将记录两两比较, 并按前小后大 ( 或前大后小 ) 规则交换 2 优点 : 每趟结束时, 不仅能挤出一个最大值到最后面位置, 还能同时部分理顺其他元素 ; 一旦下趟没有交换发生, 还可以提前结束排序例 : 关键字序列 T=(21, 25, 49, 25*, 16, 08 ), 请按从小到大的顺序, 写出冒泡排序的具体实现过程初态 : 第 1 趟第 2 趟第 3 趟第 4 趟第 5 趟 21, 25, 49, 25*, 16, 08 21, 25, 25*, 16, 08, 49 21, 25, 16, 08, 25*, 49 21, 16, 08, 25, 26

27 C 语言实现 void BubbleSort(DataType a[], int n) } { int i, j, flag = 1; DataType temp; for(i = 1; i < n && flag == 1; i++) { flag = 0; } for(j = 0; j < n-i; j++) { if(a[j].key > a[j+1].key){ } flag = 1; temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } 27

28 2.1 冒泡排序的算法分析最好情况 : 初始排列已经有序, 只执行一趟起泡, 做 n- 1 次关键码比较, 不移动对象最坏情形 : 初始排列逆序, 算法要执行 n-1 趟起泡, 第 i 趟 (1 i< n) 做了 n- i 次关键码比较, 执行了 n-i 次对象交换此时的比较总次数 KCN 和记录移动次数 RMN 为 : KCN RMN = = n 1 i = 1 3 ( n n 1 i = 1 ( n i) = i) 1 2 = n( n 3 2 n( n 1) 1) 因此 : 时间效率 : O( n 2 ) 因为要考虑最坏情况空间效率 : O( 1 ) 只在交换时用到一个缓冲单元稳定性 : 稳定 25 和 25 * 在排序前后的次序未改变 28

29 2.2 快速排序冒泡排序的一种改进算法思想 : 以首记录作为轴记录, 从前后双向扫描序列, 通过交换, 实现大值记录后移, 小值记录前移, 最终将轴记录安置在一个适当的位置 ( 小值记录在前大值记录在后 ) 轴记录将原序列分割成两部分, 依次对前后两部分重新设定轴记录, 继而分别再进行快速排序直至整个序列有序 29

30 伪代码方法 Input: an array A[p, r] Quicksort (A, p, r) { if (p < r) { q = Partition (A, p, r) //q 是基准关键字的位置 Quicksort (A, p, q-1) Quicksort (A, q+1, r) } } 30

31 一趟快速排序的过程 ( parti ti on) : 附设两个指针 i 和 j, i 指向第一个关键字 ( 基准关键字 ), j 指向最后一个关键字首先从 j 所指位置开始向前查找第一个关键字小于 key 的记录, 找到后将其和 i 所指记录交换然后再从 i 所指位置开始向后查找第一个关键字大于 key 的记录, 找到后将其和 j 所指记录交换重复上述两步, 直到 i = j 为止此时, 所有比 key 小的关键字都放到左边, 所有比 key 大的关键字都放到右边 31

32 [ ] i j [ ] i j [ ] i j [ ] i j [ ] i j [ ] i j [ ] i j [ ] 46 [ ] j i 快速排序的一次划分 32

33 void quicksort(elemtype R[],int left, int right) { int i=left, j=right; ElemType temp=r[i]; while (i<j) { while ((R[j]>temp)&&(j>i)) j=j-1; if (j>i) { R[i]=R[j]; i=i+1; } while ((R[i]<=temp)&&(j>i)) i=i+1; if (i<j) { R[j]=R[i]; j=j-1; } } // 一次划分得到基准值的正确位置 R[i]=temp; if (left<i-1) quicksort(r,left,i-1); // 递归调用左子区间 if (i+1<right) quicksort(r,i+1,right); }// 递归调用右子区间 33

34 2.2 快速排序的算法效率时间复杂度 : 最好情况 ( 每次总是选到中间值作枢轴 ) T(n)=O(nlog2n) 最坏情况 ( 每次总是选到最小或最大元素作枢轴 ) T(n)=O(n²) 空间复杂度 : 需栈空间以实现递归最坏情况 : S(n)=O(n) 一般情况 : S(n)=O(log2n) 34

35 3 选择排序选择排序的基本思想是 : 每次从待排序的数据元素集合中选取关键字最小 ( 或最大 ) 的数据元素放到数据元素集合的最前 ( 或最后 ), 数据元素集合不断缩小, 当数据元素集合为空时选择排序结束常用的选择排序算法 : ( 1 ) 直接选择排序 ( 2 ) 堆排序 35

36 3.1 直接选择排序 1 其基本思想每经过一趟比较就找出一个最小值, 与待排序列最前面的位置互换即可 ( 即从待排序的数据元素集合中选取关键字最小的数据元素并将它与原始数据元素集合中的第一个数据元素交换位置 ; 然后从不包括第一个位置的数据元素集合中选取关键字最小的数据元素并将它与原始数据集合中的第二个数据元素交换位置 ; 如此重复, 直到数据元素集合中只剩一个数据元素为止 ) 2 优缺点优点 : 实现简单缺点 : 每趟只能确定一个元素, 表长为 n 时需要 n-1 36 趟

37 例 : 关键字序列 T= ( 21, 25, 49, 25*, 16, 08 ), 请给出简单选择排序的具体实现过程原始序列 : 21, 25, 49, 25*, 16, 08 第 1 趟 08, 25, 49, 25*, 16, 21 第 2 趟 08, 16, 49, 25*, 25, 21 第 3 趟第 4 趟 08, 16, 21, 25*, 25, 49 08, 16, 21, 25*, 25, 49 3 算法分析第 5 趟 08, 16, 21, 25*, 25, 49 时间效率 : O( n 2 ) 虽移动次数较少, 但比较次数仍多空间效率 : O( 1 ) 没有附加单元 ( 仅用到 1 个 temp) 算法的稳定性 : 不稳定 37

38 c 语言程序 void SelectSort(DataType a[], int n) { int i, j, small; DataType temp; } for(i = 0; i < n-1; i++) { small = i; for(j = i+1;j<n;j++) if(a[j].key < a[small].key) small=j; if(small!= i){ temp = a[i]; } } a[i] = a[small]; a[small] = temp; 38

39 3.2 堆排序堆的定义 : n 个元素的序列 ( k1, k2,, kn ), 当且仅当满足下列关系时, 称之为堆 : k i k 2i k i k 2i+1 k 或 i k 2i ( i=1,2,... n/2 ) K i k 2i+1 若将此排序码按顺序组成一棵完全二叉树, 则 ( 1 ) 称为小根堆 ( 二叉树的所有根结点值小于或等于左右孩子的值 ),( 2 ) 称为大根堆 ( 二叉树的所有根结点值大于或等于左右孩子的值 ) 39

40 1 ( 96, 83, 27, 38, 11, 9 ) ( 13, 38, 27, 50, 76, 65, 49, 97 ) 一个堆对应一棵完全二叉树

41 由例 1 和例 2 可以看出, 如果一个序列 ( k1, k2,, kn ) 是堆, 则堆顶元素 ( 或完全二叉树的根结点 ) 必定为序列中 n 个元素的最小值或最大值因此, 在输出堆顶元素之后, 如果把剩余的 n - 1 个元素重新建成一个堆, 则可以得到 n 个元素中的次小值如此反复建立堆并输出堆顶元素, 则可以得到一个有序的序列这个过程就称为堆排序 41

42 由此可见, 堆排序必须解决两个问题 : 如何由一个无序序列建成一个堆? 其实本质就是一个反复筛选调新堆的过程如何在输出堆顶元素之后, 调整剩余元素, 使之成为一个新的堆? 42

43 在输出堆顶元素之后, 可以使用筛选法, 来调整剩余的元素, 使之成为一个新堆 (1) 如何调整建堆筛选法 : 输出堆顶元素之后, 以堆中最后一个元素替代之 ; 然后将根结点值与左右子树的根结点值进行比较, 并与其中小者进行交换 ; 重复上述操作, 直至叶子结点, 将得到新的堆, 称这个从堆顶至叶子的调整过程为筛选 43

44 例输出堆顶元素 13, 将堆中最后一个元素 91 代替堆被破坏, 把根结点 91 与其右孩子 27 交换 44

45 右子树不满足堆, 将其根 91 与右孩子 49 交换新堆建成, 新的堆顶元素是 27 45

46 练习题 1 : 关键字序列为 { 24, 10, 90, 77, 16, 25, 33, 89, 67 }, 下图为由关键字序列建立的初始堆, 请给出删去堆顶元素 10 之后整理堆的过程

47 把 10 和堆底元素 77 交换后, 需将 77 和 16 交换将 77 和 24 交换 47

48 重新整理好堆, 新的堆顶元素是

49 (2) 建初始堆现在讨论对 n 个元素初始建堆的过程建堆方法 : 对初始无序序列建堆的过程, 就是一个反复进行筛选的过程对于有 n 个结点的完全二叉树, 其最后一个非终端结点是第 n/2 个元素, 因此, 筛选只需从第 n/2 个元素开始对所有非终端结点进行 49

50 例 a.8 个结点的初始状态 b. 从第 4 个结点开始筛选 50

51 c. 对第 3 个结点开始筛选 91 d. 以第 2 个结点为根的子树已经是堆, 不用筛选 51

52 e. 对根结点筛选 : 初始堆如图

53 ( 3) 堆排序的过程 : ( 实例讲解 ) 对 n 个元素的序列进行堆排序, 先将其建成堆, 把根结点与第 n 个结点交换 ; 调整前 n- 1 个结点成为堆, 再把根结点与第 n- 1 个结点交换 ; 重复上述操作, 直到整个序列有序假设 : 关键字序列为 { 24, 10, 90, 77, 16, 25, 33, 89, 67 }, 请给出建初始堆的过程 53

55 ( 4 ) 堆排序算法分析 : 时间效率 : O(nlog 2 n) 因为整个排序过程中需要调用 n-1 次堆顶点的调整, 而每次堆排序算法本身耗时为 log 2 n ; 空间效率 : O(1) 仅在第二个 for 循环中交换记录时用到一个临时变量 temp 稳定性 : 不稳定优点 : 对小文件效果不明显, 但对大文件有效 55

56 4 归并排序 4.1 归并排序的基本思想是: 将两个 ( 或以上 ) 的有序表组成新的有序表 ( 归并排序主要是二路归并排序 ) 4.2 二路归并排序 : 可以把一个长度为 n 的无序序列看成是 n 个长度为 1 的有序子序列, 首先做两两归并, 得到 n / 2 个长度为 2 的有序子序列 ; 再做两两归并,, 如此重复, 直到最后得到一个长度为 n 的有序序列例 : 关键字序列 T= ( 21, 25, 49, 25*, 93, 62, 72, 08, 3 7, 16, 54 ), 请给出归并排序的具体实现过程 56

len=1 len=2 21 25 49 25* 93 62 72 08 37 16 54 21 25 25* 49 62 93 08 72 16 37 54 len=4 21 25 25* 49 08 62 72 93

57 len=1 len= * * len= * len= * len= * 整个归并排序仅需 log 2 n 趟 57

58 一次二路归并排序算法的 C 语言程序 void Merge(DataType a[], int n, DataType swap[], int k) /*k 为有序子数组的长度, 一次排序后的有序子序列存于数组 swap 中 */ { int m = 0, u1,l2,i,j,u2; int l1 = 0; /* 第一个有序子数组下界为 0*/ while(l1+k <= n-1) { l2 = l1 + k; /* 计算第二个有序子数组下界 */ u1 = l2-1; /* 计算第一个有序子数组上界 */ u2 = (l2+k-1 <= n-1)? l2+k-1: n-1;/* 计算第二个有序子数组上界 */ /* 两个有序子数组合并 */ for(i = l1, j = l2; i <= u1 && j <= u2; m++) { if(a[i].key <= a[j].key) { swap[m] = a[i]; i++; 58

59 else { swap[m]=a[j]; j++; } } /* 子数组 2 已归并完, 将子数组 1 中剩余的元素存到数组 swap 中 */ while(i <= u1) { swap[m] = a[i]; m++; i++; } /* 子数组 1 已归并完, 将子数组 2 中剩余的元素存到数组 swap 中 */ } while(j <= u2) { swap[m] = a[j]; m++; j++; } l1 = u2 + 1; /* 将原始数组中只够一组的数据元素顺序存放到数组 swap 中 */ for(i = l1; i < n; i++, m++) swap[m] = a[i]; 59

60 4.3 二路归并排序算法分析 : 时间效率 : O(nlog 2 n) 因为在递归的归并排序算法中, 函数 Merge( ) 做一趟两路归并排序, 需要调用 merge ( ) 函数 n/(2len) O(n/len) 次, 而每次 merge( ) 要执行比较 O(len) 次, 另外整个归并过程有 log 2 n 层, 所以算法总的时间复杂度为 O(nlog 2 n) 空间效率 : O(n) 因为需要一个与原始序列同样大小的辅助序列这正是此算法的缺点稳定性 : 稳定 60

Microsoft PowerPoint - ds-1.ppt [兼容模式]

Microsoft PowerPoint - ds-1.ppt [兼容模式] http://jwc..edu.cn/jxgl/ HomePage/Default.asp 2 说明总学时 : 72( 学时 )= 56( 课时 )+ 16( 实验 ) 行课时间 : 第 1 ~14 周周学时 : 平均每周 4 学时上机安排待定考试时间 : 课程束第 8 11 12 章的内容为自学内容 ; 目录中标有