北航数据结构课件第十章.pps

10.4 泡排序法,10.2 插入排序法,10.3 选择排序法,10.5 谢尔( Shell )排序法,10.6 快速排序法,10.7 堆积排序法,10.8 二路归并排序法,10.1 排序的基本概念,10.2 插入排序法,第i 趟排序将序列的第i+1个元素ki+1插入到一个大 小为i ,且已按值有序的序列 k1, k2, , ki 的合适位置， 得到一个大小为i+1， 并且仍然保持按值有序的序列 k1 , k2, , ki+1。, 38 49 76 97 65 13 27 50,65,65,temp,97,76,65,38 49 65 76 97 13 27 50,38 49 97 76 65 13 27 50,38 49 97 76 65 13 27 50,49,38 49 76 97 65 13 27 50,13 27 38 49 65 76 97 50,13 38 49 65 76 97 27 50,38 49 65 76 97 13 27 50,13 27 38 49 50 65 76 97,13 38 49 65 76 97 27 50,27,low,high,mid,27,high,high,mid,mid,low,low,mid,high,high,mid,1. 排序的时间效率与什么直接有关？,答案： 与排序过程中元素之间的比较次数直接有关。,2. 若原始序列为一个按值递增的序列，则排序过程 中一共要经过多少次元素之间的比较？,答案： 由于每一趟排序只需要经过一次元素之间的比较就可以找到被插入元素的合适位置，因此，整个n-1趟排序一共要经过n-1 次元素之间的比较。,3. 若原始序列为一个按值递减的序列，则排序过程 中一共要经过多少次元素之间的比较？,若以最坏的情况考虑，则插入排序算法的时间 复杂度为 O(n2).,10.3 选择排序法,1,n,2,n-1,3,n-2,每一趟排序从序列中没有排好序的元素中选择一个值最小的元素，与没有排好序的元素最前面那个元素交换位置。, ,13 97 38 76 65 49 27 50,13 27 38 49 50 65 76 97,13 27 38 76 65 49 97 50,13 27 38 76 65 49 97 50,13 27 38 49 65 76 97 50,13 27 38 49 50 76 97 65,13 27 38 49 50 65 97 76,若原始序列为一个按值递增的序列，则排序过程 中一共要经过多少次元素之间的比较？若原始序列为 一个按值递减的序列，则排序过程中又要经过多少次 元素之间的比较？,选择排序算法的时间复杂度为O(n2)。,结论：选择排序法的元素之间的比较与原始序列的 状态无关。,10.4 泡排序法,49 97 38 13 27 50 76 65,49 38 13 27 50 76 65 97,38 13 27 49 50 65 76 97,13 27 38 49 50 65 76 97,13 27 38 49 50 65 76 97,10.5 谢尔(Shell)排序法,初 始 49 97 38 50 76 65 13 27 25,d=4,49 97 38 50 76 65 13 27 25,25 65 13 27 49 97 38 50 76,d=2,25 65 13 27 49 97 38 50 76,13 27 25 50 38 65 49 97 76,13 27 25 50 38 65 49 97 76,d=1,13 25 27 38 49 50 65 76 97,10.6 快速排序法,4,s : 当前参加排序的那些元素的第一个元素在 序列中的位置，初始值为1。 t ： 当前参加排序的那些元素的最后那个元素 在序列中的位置, 初始值为n 。,temp: 保存分界元素.,i, j : 两个位置变量，初始值分别为s 与t+1.,方法 一,1. 反复执行动作ii+1，直到tempKi或者i=t。 反复执行动作jj-1，直到tempKj或者j=s。,2. 若i j，则Ki与Kj交换位置，转到第1步。,3. 若i j，则Ks 与 Kj 交换位置，到此，分界元素 Ks的最终位置已经确定，然后对被Ks分成的两 部分中大小大于1 的部分重复上述过程，直到排序 结束。,49 38 65 97 76 27 13 50,i,j=t+1,步骤,procedure QUICKSORT( K, s, t ) if (st) then is jt+1 tempKs loop repeat ii+1 until (tempKi or i=t) repeat jj-1 until (tempKj or j=s) if (ij) then call SWAP( Ki, Kj ) else exit forever call SWAP( Ks, Kj ) call QUICKSORT( K, s, j-1) call QUICKSORT( K, j+1, t) end,方法 二,s : 当前参加排序的那些元素的第一个元素在 序列中的位置，初始值为1。 t ： 当前参加排序的那些元素的最后那个元素 在序列中的位置, 初始值为n 。,temp: 保存分界元素.,i, j : 两个位置变量，初始值分别为s+1 与s.,1. 当 it 时，执行以下动作 (1). jj+1 (2). 交换元素Ki与Kj的位置。,2. 交换元素Ks与Kj的位置。到此，分界元素 Ks的最终位置已经确定，然后对被Ks分成的两 部分中大小大于1的部分重复上述过程，直到排序 结束。,步骤,10.7 堆积排序法,50 23 41 20 19 36 4 12 18,称满足条件(1)的堆积为大顶堆积，称满足条件(2)的堆 积为小顶堆积。,例,三.堆积排序法的步骤,二.堆积排序法的核心思想,1. 将原始序列转换为第一个堆积。,2. 将堆积的第一个元素与堆积的最后那个元素交换 位置。（即“去掉”最大值元素）,3. 将“去掉”最大值元素后剩下的元素组成的子序列 重新转换一个新的堆积。,4. 重复上述过程的第2至第3步n1 次。,50 23 41 20 19 36 4 12 18 10,10 23 41 20 19 36 4 12 18 50,41 23 36 20 19 10 4 12 18 50,18 23 36 20 19 10 4 12 41 50,36 23 18 20 19 10 4 12 41 50,12 23 18 20 19 10 4 36 41 50,（一趟结束）,四.调整子算法,五.建初始堆积,75 36 18 53 80 30 48 90 15 37,90 80 48 53 75 30 18 36 15 37,依次将编号为i 的结点为根的二叉树转换为一个 堆积，每转换一棵子树，做一次i 减1，重复上述过程， 直到将i=1的结点为根的二叉树转换为堆积。,i=n/2,75 36 18 53 80 30 48 90 15 37,90 80 48 53 75 30 18 36 15 37,原 始,37 80 48 53 75 30 18 36 15 90,80 75 48 53 37 30 18 36 15 90,15 75 48 53 37 30 18 36 80 90,第1 趟,第2 趟,75 53 48 36 37 30 18 15 80 90,15 53 48 36 37 30 18 75 80 90,第3 趟,53 37 48 36 15 30 18 75 80 90,18 37 48 36 15 30 53 75 80 90,第4 趟,48 37 30 36 15 18 53 75 80 90,18 37 30 36 15 48 53 75 80 90,第5 趟,37 36 30 18 15 48 53 75 80 90,15 36 30 18 37 48 53 75 80 90,第6 趟,36 18 30 15 37 48 53 75 80 90,15 18 30 36 37 48 53 75 80 90,第7 趟,30 18 15 36 37 48 53 75 80 90,15 18 30 36 37 48 53 75 80 90,第8 趟,第9 趟,18 15 30 36 37 48 53 75 80 90,15 18 30 36 37 48 53 75 80 90,六.堆积排序算法,10.8 二路归并排序法,一.什么是二路归并？,将两个位置相邻、并且各自按值有序的子序列合并为 一个按值有序的子序列的过程称为二路归并。,( Ks, Ks+1, Ks+2, , Kt ),( Kt+1, Kt+2, Kt+3, , Ku ),( Xs, Xs+1, Xs+2, Xs+3, , Xu ),KsKs+1 Ks+2 Kt,Kt+1 Kt+2 Kt+3 Ku,Xs Xs+1 Xs+2 Xs+3 Xu,（12, 45, 78, 90, 100, 125),（27, 32, 51, 93 ),( 12, 27, 32, 45, 51, 78, 90, 93, 100, 125 ),i,j,q,procedure MERGE( X, s, t, u, Z ) is jt+1 qs while ( it and ju ) do if (XiXj) then ZqXi ii+1 else ZqXj jj+1 qq+1 end,while (it) do ZqXi ii+1 qq+1 end while (ju) do ZqXj jj+1 qq+1 end end,合并算法,二.二路归并排序法的核心思想,39 12 48 27 62 94 80 33,12 39,27 48,62 94,33 80,12 27 39 48,33 62 80 94,12 27 33 39 48 62 80 94,第1 趟,第2 趟,第3 趟,39 12 48 27 62 94 80 33