《设计 郑宗汉郑晓明 第3章+排序问题和离散集合的操作》由会员分享，可在线阅读，更多相关《设计 郑宗汉郑晓明 第3章+排序问题和离散集合的操作（49页珍藏版）》请在金锄头文库上搜索。
1、第第3 3章章 排序问题和离散集合的操作排序问题和离散集合的操作 3.1 合并排序 3.2 堆排序 3.3 基数排序 3.4 离散集合的操作3.1 合并排序3.1.1 合并排序算法的实现 假定要排序的数据有8个, 第一步划分为 4对, 每对2个元素, 用merge算法合并成4 个有序序列; 第二步把4个序列划分成2 对, 用merge算法合并成2个有序的序列; 最后用merge算法合并成1个有序序列。 算法3.1 合并排序算法输入: n元素数组A; 输出:递增序数组A void merge_sort(Type A, int n) int i, s, t=1; /i:开始时第1个序列起始处;/s
2、:合并前序列大小; t:合并后序列大小 while (tn, 退 出内部while循环; i+s=11不小于n, 不 执行if语句体, 余下一个元素没处理。第二轮循环, s=2, t=4, 有2对2元素序 列进行合并。当i=8时, i+t=12n, 退出 内部while循环; i+s=10n, 退出内部 while循环; i+s=12n, 不执行if语句体, 余留一个序列没有处理。 第四轮循环, s=8, t=16。在i=0时, i+t=16n, 不执行内部while循环; i+s=8n, 退出外部 while循环。3.1.2 合并排序算法的分析 1. 时间复杂性分析假定n=2k。merge比
3、较次数至少min(n1,n2), 至多是n-1。 外部while循环体执行次数: k=logn 内部while merge 比较总次数 merge次数 比较次数 最少 最多 第1轮 n/2 1 (n/2)1 (n/2)1 第2轮 n/22 21,22-1=3 (n/22)21 (n/22)(22-1) 第3轮 n/23 22,23-1=7 (n/23)22 (n/23)(23-1) 第j轮 n/2j 2j-1,2j-1 (n/2j)2j-1 (n/2j)(2j-1)第j轮: 至少为(n/2j)2j-1, 至多为(n/2j)(2j-1) 合并排序算法的执行时间:至少为: j=1k(n/2j)2j
4、-1= n/2k =1/2nlogn 至多为: j=1k (n/2j)(2j-1) = j=1k(n-n/2j) = kn-n(1/2+1/22+1/2k)= kn-n(1-1/2k) = kn-n+1 = nlogn-n+1 故合并排序为(nlogn), O(nlogn), (nlogn)2. 空间复杂性 每调用一次merge便分配一个适当大小的 缓冲区, 退出merge便释放它。最后一次调用merge所分配的缓冲区最大 , 此时把两个序列合并成一个长度为n的 序列, 需要(n)个工作单元。故合并排序算法的空间复杂度为(n)。 3.2 堆排序3.2.1 堆的定义及性质定义3.2 n个元素称为
5、最小堆 当且仅当 关键字序列满足: kik2i, kik2i+1; n个元素称为最大堆 当且仅当 关键字 序列满足: kik2i, kik2i+1。 堆的性质:若堆的高度为d, 则 1. 所有叶结点处于第d层或d-1层; 2. 当d1时, 第d-1层上有2d-1个结点; 3. 若第d-1层上有分支结点, 则这些分支结点都在树的最左边; 4. 对最大堆, 每个结点的关键字都大于其子结点关键字; 对最小堆, 每个结点的关键字都小于其子结点关键字。堆的存储方式:用数组H存放具有n个元素的堆 1. 根结点存放在H1; 2. 假定结点x存放在Hi, 若它有左儿子, 则其左儿子结点存放在H2i; 若它有右
6、儿子, 则右儿子结点存放在H2i+1; 3. 非根结点Hi的父结点存放在Hi/23.2.2 堆的操作一般地, 堆可进行如下几种操作: void sift_up(Type H , int i);把堆H中第i个元素上移 void sift_down(Type H , int n, int i);把堆H中第i个元素下移 void insert(Type H , int 把元素x插入堆H中void delete(Type H , int 删去堆H中第i个元素 Type delete_max(Type H , int 从非空最大堆中删除并回送最大元素 void make_heap(Type H , in
7、t n);使数组H中元素按堆的结构重新组织3.2.2.1 元素上移操作 以最大堆为例。修改堆中元素可能违反 堆的性质，需进行元素上移或下移。元素上移：沿着Hi到根的路线，把Hi 向上移动。在移动过程中，若大于其父 结点，则与父结点交换位置，否则操作 结束。算法3.2 元素上移操作输入: 数组H及被上移的元素下标i 输出: 维持堆性质的数组H 1. void sift_up(Type H, int i) 2.Bool done = False; 3. if (i != 1) 4. while (!done 6. else done = True; 7. i = i/2; 执行时间: O(logn
8、); 工作单元: (1)例3.1 把图中结点9的内容改为28的过程 3.2.2.2 元素下移操作 以最大堆为例。修改堆元素可能违反堆 的性质，需进行元素上移或下移。元素下移：在下移过程中，把其关键字 与两个子结点中关键字较大的子结点进 行比较，若小于其子结点的关键字，则 与子结点交换位置，否则操作结束。算法3.3 元素下移操作输入: 数组H, 元素个数n,下移元素下标i 输出: 维持堆性质的数组H void sift_down(Type H, int n, int i) Bool done = False;if (2*i)Hi) i=i+1;if(Hi/2=x) sift_up(H, i);
9、else sift_down(H,n,i); 执行时间: O(logn); 工作单元: (1) 3.2.2.5 删除关键字最大的元素 最大堆中最大元素位于根结点，借助于 delete操作，既做删除操作，又维持堆的 性质。算法3.6 删除关键字最大元素输入: 数组H, 数组元素个数n 输出: 数组H, 被删元素, 删后元素个数n Type delete_max(Type H, int x=H1; delete(H,n,1); return x; 执行时间: O(logn); 工作单元: (1) 3.2.3 堆的建立: 两种方法1. 用insert操作建造堆 算法3.7 建造堆的第一种算法 输入:
10、 数组A, 数组的元素个数n 输出: n个元素的堆H void make_heap1(Type A, Type H, int n) int i, m=0;for (i=0; i=1;i-) sift_down(A,n,i); 例3.3 把11个元素的数组调整为堆的过程: make_heap的运行时间分析1. 数组有n个元素, 二叉树高度为logn; 2. 第i层元素Aj最多下移k-i层, 最多执行2(k-i)次元素比较;3. 第i层上共有2i个结点, 第i层上所有结点最多执行2(k-i)2i次元素比较; 4. 第k层元素都是叶结点, 无需下移.最多只需对第0到k-1层元素进行下移 .令n=2k
11、, 即k=logn, 则有 故 make_heap的元素比较次数为:故 make_heap的执行时间为O(n)。此外, 每个结点作下移操作时, 至少需 做两次元素比较, 共n/2个结点作下 移操作, 至少需要2n/2次元素比较, 执行时间为(n)。因此, make_heap执行时间为(n)。 工作单元: (1)3.2.4 堆排序 假定数组A的元素数为n。把A中元素组 织为最大堆, A1为最大元; 交换A1和 An, 使An为最大元; 再对A1做下移 操作, 使A1An-1为最大堆。交换A1和An-1, 使An-1为余下元素 的最大元; 对A1做下移操作, 使 A1An-2成为最大堆。以此类推,
12、 直至新堆元素数为1, 此时, A1为最小元。算法3.9 堆排序算法输入: 数组H, 数组元素个数n 输出: 递增排序的数组A void heap_sort (Type A, int n) int i;make_heap(A, n); for (i=n, i1; i-) swap(A1, Ai); sift_down(A, i-1, 1); 堆排序的性能分析执行时间:make_heap的执行时间为(n) sift_down执行n-1次,每次花费时间O(logn),总花费时间O(nlogn)故heap_sort运行时间是O(nlogn)工作空间: (1) 基于比较的排序算法, 下界(nlogn)
13、; 基数排序方法不是基于比较的方法, 按此 法设计的算法几乎都按线性时间运行。 3.3.1 基数排序算法的思想方法 令L=a1,a2,an是一个具有n个元素的链 表, 每个元素关键字的值都由k个数字组 成, 即 dkdk-1d1, 0di9, 1ik 。3.3 3.3 基数排序基数排序 1. m=1; 2. 按关键字数字dm, 把元素分到10个链表L0,L1,L9中, 使dm=i的元素都在链表Li中; 3. 把10个链表按下标由0到9的顺序重新链成一个新链表; 4. m=m+1, 若mk, 则转2, 否则结束.例3.4 假设链表中有10个元素, 其关键字值分别为: 3097, 3673, 29
14、85, 1358,6138, 9135, 4782, 1367, 3684, 0139Step 1. 按关键字中数字d1把L中元素分到链表L0L9的情况如下:L0 L1 L2 L3 L4 L5 L6 L7 L8 L94782 3673 3684 2985 3097 1358 0139 9135 1367 6138 把L0L9中元素顺序链接, L中元素顺序:L: 4782 3673 3684 2985 9135 30971367 1358 6138 0139 Step 2. 按关键字中数字d2把 L中元素分到链表L0L9的情况如下:L0 L1 L2 L3 L4 L5 L6 L7 L8 L99135 1358 1367 3673 4782 30976138 36840139 2985 把L0L9中元素顺序链接, L中元素顺序:L: 9135 6138 0139 1358 1367 36734782 3684 2985 3097 Step 3. 按关键字中数字d3把 L中元素分到链表L0L9的情况如下:L0 L1 L2 L3 L4 L5 L6 L7 L8 L9 3097 9135 1358 3673 4782 29856138 1367 36840139 把L0L9
