18

Size: px

Start display at page:

Download "18"

慢詹
5 years ago
Views:

1 孙猛年 12 月 14 日 1

2 2

3 排序的基本概念插入排序 3

4 假设给定一个有待排序的文件, 它由 N 个记录的集合构成 :{R 1,R 2,, R N } 每个记录 R i 有一个排序码 ( 不不一定是关键码 ), 记为 K i 在排序码上确定一个全序关系 <, 使得对任意的三个排序码值 a, b, c, 下列列条件成立 : (1) a<b, a=b, b<a 三个可能性中恰有一个为真 ; (2) 如果 a<b 且 b<c, 则 a<c 排序的目标是确定下标为 {1,2,,N} 的一个排列列 p(1),, p(n), 使得 K p(1) K p(2) K p(n) 4

5 在排序的讨论中, 并不不关心被排序对象本身的逻辑结构, 可以把排序看成是字典上的一种操作排序码可以就是关键码, 也可以不不是关键码在后一种情况下, 不不同记录的排序码可以相同与关于索引的讨论类似, 在具体排序算法中, 只关心排序码的作用和表示, 而把记录中的其它字段隐藏起来 5

6 作为排序对象的文件可以是外存的数据, 也可以是内存的数据待排序的记录在排序过程中全部存放在内存的成为内排序 ; 否则称为外排序我们主要关注内排序算法从算法的基本思想出发大致可以将 ( 内 ) 排序算法分为 5 类 : 插入排序 ; 选择排序 ; 交换排序 ; 分配排序 ; 归并排序 ( 也可用于外排序 ) ( 每一类方法可能具体有多个不不同算法 ) 6

7 排序算法的主要操作 : 比较 + 记录移动 ( 调整 ) 评价排序算法好坏的主要标准 : (1) 执行行算法所需的时间 ( 最坏或者平均时间 ); (2) 执行行算法所需要的附加空间 ; (3) 算法本身的复杂程度其它标准 : 稳定性 : 若某种排序方法保持相同排序码记录的原有的相对次序, 则称这种排序方法是稳定的, 否则是不不稳定的适应性 : 如果实际的待排序序列列比较接近排好序的形式, 算法能否更更快完成工作 7

8 有助于查找 ( 例例如有序顺序表的二分法查找, 在等概率的情况下构造最佳二叉排序树 ); 解决一起性的问题, 即把一个结构中具有相同标志 ( 排序码 ) 的所有项连在一起 ; 处理理在两个或者多个结构中的具有相同标志的项 ( 例例如有序顺序表表示的两个集合的交运算 ) 8

9 插入排序的基本思想 : 每步将一个待排序的记录, 按其排序码大小, 插入到前面已经排序的文件中的适当位置, 直到全部记录都被插入完为止直接插入排序表插入排序二分法插入排序 Shell 排序多表插入排序 9

10 基本思想 : 假定待排序的 n 个记录 {R 0,R 1,,R n-1 } 存在数组中, 直接插入法在插入记录 R i (i=1,2 n-1) 时, 记录序列列分为两个区间 [R 0,R i-1 ] 和 [R i,r n-1 ], 前一区间里里的记录已排好序, 后一区间尚未排序对 R i 的处理理就是排序码 K i 依次与 K i-1, K i-2,,k 0 比较, 找出适当位置将 R i 插入, 原位置的记录向后顺移 < < R i R n-1 0 i-1 < < < < R i R n-1 0 k i 10 R i+1 R i+1

11 typedef int KeyType; typedef int DataType; typedef struct{ KeyType key; /* 排序码字段 */ DataType info; /* 记录的其它字段 */ }RecordNode; typedef struct{ int n; /* 文件中的记录个数, 可以视为常量量 */ RecordNode *record; }SortObject; 11

12 void insertsort(sortobject * pvector) { int i, j; RecordNode temp; } RecordNode *data = pvector->record; /* 引入 data 使下面代码更更简洁 */ for( i = 1; i < pvector->n; ++i) { /* 依次插入 R 1, R 2,,R n-1 */ } temp = data[i]; for ( j = i-1; temp.key < data[j].key && j >= 0; j-- ) /* 由后向前找插入位置, 排序码大于 k i 的记录后移 */ data[j+1] = data[j]; if( j!= i-1 ) data[j+1] = temp; /* j == i-1 时不不用复制 */ 稳定排序 12

13 初始 : [49] i=1: [38 49] i=2: [ ] i=3: [ ] i=4: [ ] i=5: [ ] i=6: [ ] 49 i=7: [ ] 保持原来顺序 13

14 主要关注比较次数和移动次数 : 最小比较次数 : C min =n-1 n; 最大比较次数 : C max = n-1 i=1 i=n(n-1)/2 n 2 /2; 最小移动次数 ( 包括附加记录空间 x 移动次数 ): M min =n-1 n; 最大移动次数 : M max = n-1 i=1 (i+1) =(n+2)(n-1)/2 n 2 /2 插入记录 R i-1 的平均比较次数 : i-1 j=0 P j C j = i-1 j=0 (j+1)/i=(i+1)/2 ; 直接插入排序的总的比较次数为 : n-1 j=1 (j+1)/2=o(n 2 ) 平均移动次数 : O(n 2 ) 直接插入排序算法的平均时间复杂度为 T(n) = O(n 2 ) 具有适应性空间复杂度为 S(n) = O(1) ( 附加的记录空间 x) 14

15 表插入排序的目标 : 在直接插入排序的基础上减少记录移动的次数基本思想 : 在每个记录中增加一个链接字段, 指向下一个记录, 整个被排序的文件表示成一个记录的单链表插入记录 R i 时, R 0 至R i-1 已经排序, 为了了确定插入的位置, 先将 R i 脱链, 再采用顺序比较的方法找到 R i 应插入的位置, 将 R i 插入链表 link < < < R 0 R 1 R i-1 R i R n-1 Λ info 15

16 struct Node; typedef struct Node ListNode; struct Node { KeyType key; /* 记录的排序码字段 */ DataType info; /* 记录的其他字段 */ ListList *next; /* 记录的指针字段 */ }; typedef ListNode *LinkList; 16

17 void listsort (LinkList * plist) { /* 表插入排序, 有头结点 */ ListNode *now, *pre, *p, *q, *head; head=*plist; pre=head->next; if(pre==null) return; now=pre->next; if(now==null) return; while( now!=null){ q=head; p=head->next; while(p!=now && p->key<=now->key) {q=p;p=p->next;} /* 循环结束找到插入位置 */ if(p==now) {pre=pre->next;now=pre->next; continue ;} /* now 应放在原位置 */ pre->next=now->next; /* 使 now 记录脱链 */ now->next=p; q->next=now; /* 将 now 记录插入链表中 */ now=pre->next; } } 17

18 ^ pre now ^ pre now ^ pre now ^ pre now 18

19 空间效率 : 临时空间是常量量的 O(1); 如果考虑链表用的额外空间 ( 除保存数据之外的空间 ), 每个记录增加了了一个链接字段, 这部分空间 S(n) = O(n) 时间效率 : 用链表方式不不需要记录移动, 摘除结点和链入结点的次数为 O(n), 但关键码比较次数仍是 O(n 2 ), 因此算法的时间复杂度仍为 O(n 2 ) 稳定性 : 从头往后找插入位置的循环里里, 通过关键码之间的小于等于关系进行行比较, 可以保证表插入排序的稳定性 19

20 基本思想 : 在直接插入法的基础上, 为了了减少插入R i+1 记录的比较次数, 改用二分法在前面已经排序的 [R 0,R i ] 找插入位置二分法插入排序只能用于顺序存储的数据每步的工作 : 用二分法在已排序的前一段找出当前记录应插入的位置 ; 取出当前记录, 将该位置之后的已排序记录顺序后移, 腾出空位后将当前记录插入 R i+1 R n-1 0 i/2 i 20

21 void binsort(sortobject * pvector) { int i, j, left, mid, right; RecordNode temp; RecordNode *data = pvector->record; for( i = 1; i < pvector->n; i++ ) { temp = data[i]; left = 0; right = i 1; /* 置已排序区间的下上界初值 */ while (left <= right) { mid=(left+right)/2; /* mid 指向已排序区间的中间位置 */ } if (temp.key<data[mid].key) right=mid-1; /* 插入元素应在左子区间稳定排 */ else left=mid+1; /* 插入元素应在右子区间 */ } for(j=i-1; j>=left; j--) data[j+1] = data[j]; /* 将排序码大的记录后移 */ if(left!=i) data[left] = temp; } 序 21

22 初始 : [49] i=6: [ ] 49 (1): [ ] 49 left=0 mid=3 right=6 (2): [ ] 49 left=4 mid=5 right=6 (3): [65] left=4 right=4 mid=4 49<65 right=3<left=4, 查找结束 (4):

23 二分法插入排序的比较次数与待排序记录的初始状态无关, 仅依赖于记录的个数插入第 i 个记录时, 如果 i=2 j,(0 j log 2 n ), 则要经过 j=log 2 i 次比较才能确定插入位置 ; 如果 2 j <i 2 j+1, 则比较次数为 j+1 将 n 个记录 (n=2 k ) 排序的总比较次数为 i=1 n log 2 i n*log 2 n 当 n 比较大时, 比直接插入排序的最大比较次数 O(n 2 ) 小, 但比最小比较次数 O(n) 大移动次数为 O(n 2 ) 因此平均时间复杂度 T(n)=O(n 2 ) 空间复杂度为 S(n)=O(1) ( 附加的记录空间 x) 23

24 又称缩小增量量的排序 (Diminishing Increment Sort) Shell (1959) 认为 : 排序较慢的原因是元素移动太慢, 可能经过许多步才能到达最终位置 ( 如插入排序中位于前面的大关键码记录 ); 若能加大元素的移动步伐, 就可能加快排序 Shell 提出的想法 : 把一个序列列看成由间距 d 的元素构成的 d 个子序列列反复做: (1) 在每个子序列列内部分别排序 ; (2) 缩小d 之后重复第 1 步, 直到 d 缩小为 1 时再做一次排序 ( 这也就是整个序列列排序 ) 24

25 Shell 排序希望 : 前面各遍排序可以使距离目标位置很远的元素大步迁移到目标位置的附近, 后续排序主要是局部调整, 希望局部调整可以用较少时间完成 d 1 =4 d 2 =2 d 3 =1 25

26 Shell 排序通过许多次排序实现整个序列列的排序这一策略略保证成功, 因为只有最后一次排序就足够了了非形式算法 : inc = d # d < n while ( inc > 0 ): 对相距 inc 的各组记录做直接插入排序 inc = decrease (inc) 26

27 Shell 排序可以看作一种排序模式, 其中需要 : 选择一种基本排序算法做分组的排序这一排序算法必须有适应性, 因前面排序已把大元素移向右, 小元素移向左, 后面遇到的是接近排序的序列列例例如采用直接插入排序确定一种减小间距值 d 的模式常用每次间距 d 减小一半, 即 d 1 = n/2 ;d i+1 = d i /2 (Shell) 27

28 void shellsort(sortobject * pvector, int d) { int i, j, inc; RecordNode temp, *data = pvector->record; } for (inc = d; inc > 0; inc /= 2) { /* inc 为当时增量量 */ } for (i = inc; i < pvector->n; i++) { /* 同时做 inc 个序列列排序 */ } temp = data[i]; /* 保存待插入记录 Ri*/ for (j = i - inc; j >= 0 && temp.key < data[j].key; j -= inc) /* 按间隔 inc 寻找插入点 */ data[j+inc] = data[j]; /* 大记录后移 */ data[j+inc] = temp; /* 插入记录 Ri */ 28

29 初始 : d 1 =4 d 2 = d 3 = 排序结果 :

30 采用上述常见模式 ( 插入排序和间距减半 ),Shell 排序的平均比较次数和平均移动次数都为 O(n 1.3 ) 左右 ; The Art of Computer Programming 第 3 卷 : 排序与检索 Shell 排序算法只需常量量的辅助空间 ; 一般说,Shell 排序不不能实现稳定排序 30

31 d i Shell 最早提出 d 1 = n/2,d i+1 = d i /2, 一般认为 d i 都取成奇数 d i 之间互素为好, 究竟如何选取 d i 最好? 进一步的相关问题可以参考 Knuth 的 The Art of Computer Programming 第 3 卷 31

32 32

33 直接插入排序二分法插入排序表插入排序希尔排序 * 多表插入排序 33

19

孙猛 http://www.math.pku.edu.cn/teachers/sunm 2017 年 12 月 21 日 1 选择排序交换排序 2 基本思想 : 维护最小的 i 个记录的已排序序列列 ; 每次从剩余未排序的记录中选取关键码最小的记录, 排在已排序序列列之后, 作为序列列的第 i +1 个记录 ; 直接选择排序堆排序 3 以空排序序列列开始 ; 每次从未排序记录中选排序码最小的记录,