JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 《疯狂的石头》剪辑：道哥的计划 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 道哥缺乏概括能力，无法清晰表达自己的方法（算法） JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 《三国演义》剪辑：隆重对策 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 隆重对策，鞭辟入里。 三分天下，人神共奋。 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 问题：伸大义于天下 环境：曹操，…… 孙权，…… 荆州，…… 益州，…… JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 方案：跨荆州、益州…… 向西，……；向南，…… 对外，……；对内，…… 荆州之兵 + 益州，…… JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 设计算法，首先要有总括能力：分析问题准确、细致；解决问题条分缕析、主次得当。 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 第 5 章 归纳法 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 几个最基础的排序算法 选择排序 插入排序 冒泡排序 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 基数排序 整数列 L= 7467、1247、3275、6792、9187、9134、4675、1239 基数：10 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin L0= L1= L2= L3= L4= L5= L6= L7= L8= L9= 生成10个空表 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin L0= L1= 6792 L2= L3= 9134 L4= 3275、4675 L5= L6= 7467、1247、9187 L7= L8= 1239 L9= 按个位进表 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 归拢这十个表表 6792、9134、3275、4675、7467、1247、9187、1239 L= JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin L0= L1= L2= 9134、1239 L3= 1247 L4= L5= 7467 L6= 3275、4675 L7= 9187 L8= 6792 L9= 按十位进表 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 二次归拢这十个表表 9134、1239、1247、7467、3275、4675、9187、6792 L= JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin L0= 9134、9187 L1= 1239、1247、3275 L2= L3= 7467 L4= L5= 4675 L6= 6792 L7= L8= L9= 按百位进表 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 三次归拢这十个表表 9134、9187、1239、1247、3275、7467、6475、6792 L= JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin L0= 1239、1247 L1= L2= 3275 L3= 4675 L4= L5= 6792 L6= 7467 L7= L8= 9134、9187 L9= 按千位进表 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 四次归拢这十个表表 1239、1247、3275、6475、6792、7467、9134、9187 L= JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 数位不同，可以分别处理。 基数可变：2、4、8、10、16… 算法重点：生成空白表、进表 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 算法RadixSort： 输入：一张有n个非负整数的表L={a1, …, an}，每个数 k位 输出：按照非降序排列的L JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin for j =1 to k 生成 10 个空表 L0, L1, …, L9 while L 非空 a = L 中的下一个元素 L(next)；删除 L(next) i = a 中的第 j 位数字； 数 a 进表 Li end while for i = 0 to 9 L = L, Li , 将 Li 加入 L 中 end for return L JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 开始 流程图 j=1 jk？ Y 生成10个表，L0，…，L9 结束 j++ i=0 N Y L 非空？ N N i  9？ a = L(next); Delete(L(next)) i = a 的第 j 位数； a 进表 Li L = L  Li JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 算法RadixSort的复杂度：θ(kn) 思考：对于位数不相等的整数序列，如何用该算法排序？ JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 一个看似简单、直接的问题，竟然有意想不到的巧妙解法，从这可见算法设计的 魅力所在。 算法不是从地里长出来的，是人们经过艰辛的努力发现的！它们象下面的原子模型的建立过程 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 原子模型建立过程 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 启发： 大胆设计算法，不断改进之。 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 这个问题是如何计算一个实数的整数幂， xn ？ 直接求解 ：连续累乘 算法简单，效率较高！ JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 竟然有个更为高效、颇为简单的算法！！！ 如果 n 是偶数， xn = (xm)2 如果 n 是奇数，xn = x(xm)2 聪明吧！ JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 算法 EXPREC 描述 输入：实数 x 和非负整数 n 输出： xn JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin power( x, n ) 过程 power( x, m ) { 计算 xm } if m = 0 then y = 1 else y = y = y2 if m 为奇数 then y =xy end if return y JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin power( x, m )流程图 开始 y = y = y2 Y N m = 0？ y = 1 N m 是奇数？ Y y = xy 返回 y 结束 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 练习： 实现这两个算法 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 寻找多数元素——强针对性算法 多数元素——对序列A[1…n]，如果有出现次数超过 的元素，这个元素就叫该序列的多数元素。 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 办法很多 现成的办法有两个 1、一一比较，时间复杂度 O(n2) 2、排序，时间复杂度 O(nlogn) 还有，更简单的算法！！ JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 算法基础 在原序列中，消除两个不同的元素后，原序列中的多数元素仍然是新系列中的多数元素。 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 算法关隘： 如何在原序列中，不断地、高效地去除两个不同的元素，直至最后？ 显然是顺次嘛！ JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 算法步骤： 输入：n个元素的数组 A[1…n] 输出：如果存在多数元素，则输出之；否则输出 none JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin c = candidate(1) count = 0 for j = 1 to n if A[j] = c then count = count + 1 end for if count > then return c else return none JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 开始 算法流程图 c = candidate(1) count = 0 j = 1 to n N A[j]=c？ Y count ++ N Y 返回 none 返回 c 结束 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 过程：candidate( m ) j = m; c = A[m]; count = 1 while j<n && count > 0 j = j + 1 if A[j] = c then count ++ else count -- end while if j = n then return c else return candidate (j + 1) JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin m candidate( m ) 流程图 j = m; c = A[m]; count = 1 j <n && count > 0 N A[j]=c？ Y count -- count ++ N j = n ? Y 返回 candidate(j+1) 返回 c JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 如果数组中有多数元素，即使全部“非多数元素”都被用来去除“这个多数元素”，最终留下的必是这个多数元素。 思考： 如果原序列中没有多数元素，由 candidate(m) 带回来的元素 c 有什么特征？ 比如是最后一个元素？至少重复一次？…… JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 简单的证明思路： 每当消除数组中的一个多数元素，必定至少有一个 “非多数元素” 同时被消除，根据 “多数元素”的定义，最终留下的必是这个多数元素。 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 堆排序 利用二叉树构成的堆——二叉堆，对数列排序。 由于二项式堆、斐波纳契堆等使用较少，一般将二叉堆就简称为堆。 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 堆的特性： 1．父节点的键值大于或等于（小于或等于）每个子节点的键值。 2．每个节点的左子树和右子树都是一个堆。 注： 特性 1 中，前者为 “最大堆” 或者 “大顶堆”，后者为 “最小堆” 或者 “小顶堆”。 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 堆的存储：（1）二叉树 12 35 22 7 8 32 10 1 15 5 23 27 9 4 A[14] = 用数组来表示二叉树，节点 i （= 0, 1, 2, …）的父结点下标就为 (i – 1) / 2。它的左右子节点下标分别为 2 * i + 1 和 2 * i + 2。例如，第 4个节点左右子节点下标分别为 9 和 10 。见下图。 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 堆的存储：（1）二叉树例图 12 35 22 7 8 32 10 1 15 5 23 27 9 4 A[14] = 12 35 22 7 8 32 10 4 1 9 27 23 5 15 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 堆的存储：（2） 堆（最大堆） 35 23 32 15 12 27 10 1 7 5 8 22 9 4 A[14] = 35 23 32 15 12 27 10 4 1 9 22 8 5 7 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 建堆： 从最后一个中间节点开始。n = 14，不大于 n/2 的最大整数是 7 ，节点 7 的键值 = 10。按照定义，该子树是最大堆，不需要调整这两个节点的键值。 之后考察 i = 5 的节点，其键值 32，该子树也是最大堆， 但是， i = 4 的节点所在子树不是最大堆，所以要调整， …… JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 起始图： 12 35 22 7 8 32 10 4 1 9 27 23 5 15 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 注意 i = 4 、 i = 10 和 i = 3 、 i = 8 的节点键值的变化 12 35 22 15 23 32 10 4 1 9 27 8 5 7 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 继续查看 i = 2 和 i = 1 的节点，于是有下图 注意 i = 5 和 i = 11 的节点键值的变化 12 35 32 15 23 27 10 4 1 9 22 8 5 7 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 注意 i = 5 和 i = 11 的节点键值的变化 35 23 32 15 12 27 10 4 1 9 22 8 5 7 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 完成最大堆的构建 注意：每一步都要到数组中修改相应位置的元素值 35 23 32 15 12 27 10 4 1 9 22 8 5 7 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 建堆结果： 1、序列成为一个“最大堆”； 2、根节点键值是序列的最大数。 JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 堆排序： 建堆 j = , …, 1 while i = 1, …, n-1 对换节点 k = n+1-i 与节点 k = 1 Sift-down(H-i, 1) // 序列最后的 i 个元素已经排好序 end while return JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 堆的运算——上筛 Sift-up(H, i) 目标：上移 H[i] 使得他的键值不大于其父节点的 flag = 0; if(i = 1) then exit; //节点 i 为根节点 while i = 1 or flag = 1 if( H(i) > H( ) ) then 对换这两个节点 else flag = 1 i = end while return JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 堆的运算——下筛 Sift-down(H, i) 目标：下移 H[i] 使得他的键值不大于其父节点的 flag = 0; if( 2i > n ) then exit; //节点 i 为叶子节点 while 2i > n or flag = 1 i = 2i if (i+1n && H(i+1) > H( i ) ) then i = i+1 if( H(i) > H( ) ) then 对换这两个节点 else flag = 1 end while return JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 堆的运算——插入 Insert(H, x) 目标：向堆 H 中插入一个元素 x n = n+1; //增加 H 的大小 H[n] = x Sift-up(H, n) JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 堆的运算——删除 Delete(H, i) 目标：删除堆中元素 H[i] x = H[i]; y = H[n]; n = n-1 //减少 H 的大小 if( i=n+1) then exit; H[i] = y if( yx ) then Sift-up( H, i ) else Sift-down( H, i ) end if JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 堆的运算——删除最大值 DeleteMax( ) 目标：删除堆中最大元素 x x = H[1]; n = n-1 //减少 H 的大小 delete( H, 1) H[i] = y return x JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 堆的运算——建堆 MakeHeap(A) 目标：将一个 n 元数组 A，转化为一个堆 for i = down to 1 Sift-down( A, i ) end for JUFE • SCES__Dr. Aihua Yin 2019/5/10

JUFE • SCES__Dr. Aihua Yin 练习 实现这两个算法 本章结束！ JUFE • SCES__Dr. Aihua Yin 2019/5/10