1、第三章查找与排序(下)本节内容通过本单元的学习，了解、掌握有关排序的：n基本概念：n排序、排序分类、算法稳定性排序、排序分类、算法稳定性n典型的排序算法:n插入排序、选择排序、交换排序插入排序、选择排序、交换排序n归并排序、基数排序归并排序、基数排序排序的基本概念n定义：定义：将记录按将记录按关键字关键字递增递增(递减递减)的次序排列起来，的次序排列起来，形成新的有序序列，称为排序。形成新的有序序列，称为排序。n描述：描述：设设n个记录的序列为个记录的序列为R1,R2,Rn,其相应关键字序其相应关键字序列为列为K1,K2,Kn,需确定一种排序需确定一种排序P1,P2,Pn,使其使其相应的关键字
2、满足递增相应的关键字满足递增(升序升序),或递减或递减(降序降序)的关系的关系:Kp1 Kp2 .Kpn 或或 Kp1 Kp2 .Kpn3.3 基本的排序技术n虽然排序算法是一个简单的问题，但是虽然排序算法是一个简单的问题，但是从计算机科学发展以来，已经有大量的从计算机科学发展以来，已经有大量的研究在此问题上。举例而言，研究在此问题上。举例而言，冒泡排序冒泡排序在在1956年就已经被研究。虽然大部分人年就已经被研究。虽然大部分人认为这是一个已经被解决的问题，有用认为这是一个已经被解决的问题，有用的新算法仍在不断的被发明。（例子：的新算法仍在不断的被发明。（例子：图书馆排序图书馆排序在在2004
3、年被发表）年被发表）算法稳定性0 1 2 3 4 5算法稳定性算法稳定性n当相等的元素是无法分辨的，比如像是整数，当相等的元素是无法分辨的，比如像是整数，稳定性并不是一个问题。然而，假设以下的数稳定性并不是一个问题。然而，假设以下的数对将要以他们的第一个数字来排序。对将要以他们的第一个数字来排序。n(4,1)(3,1)(3,7)(5,6)n(3,1)(3,7)(4,1)(5,6)(保持次序保持次序)n(3,7)(3,1)(4,1)(5,6)(次序被改变次序被改变)n不稳定排序算法可能会在相等的键值中改变纪不稳定排序算法可能会在相等的键值中改变纪录的相对次序。录的相对次序。n不稳定排序算法可以被
4、特别地实现为稳定。方不稳定排序算法可以被特别地实现为稳定。方法是法是 人工扩充键值的比较。然而，要记住这人工扩充键值的比较。然而，要记住这种次序通常牵种次序通常牵 涉到额外的空间负担。涉到额外的空间负担。n简单起见，这里用顺序存储结构描述待排简单起见，这里用顺序存储结构描述待排序的记录。序的记录。n顺序存储结构（顺序存储结构（C语言描述）：语言描述）：#define N n typedef struct record int key；/*关键字项 */int otherterm；/*其它项其它项 */；typedef struct record RECORD；RECORD fileN+1；/*
5、RECORD型的型的N+1元数组元数组*/排序算法的数据结构典型排序算法n冒泡排序冒泡排序n快速排序快速排序n简单插入排序简单插入排序n希尔排序希尔排序n简单选择排序简单选择排序n堆排序堆排序n归并排序归并排序n基数排序基数排序n二叉排序树二叉排序树一、冒泡排序n1.指导思想：指导思想：两两比较待排序记录的关键字，并交换两两比较待排序记录的关键字，并交换不满足顺序不满足顺序要求的那要求的那些偶对元素，直到全部数列满足有序为止。些偶对元素，直到全部数列满足有序为止。n冒泡排序（冒泡排序（Bubble sort）是基于交换排序的一种算法。它是是基于交换排序的一种算法。它是依次两两比较待排序元素；若
6、为逆序（递增或递减）则进行依次两两比较待排序元素；若为逆序（递增或递减）则进行交换，将待排序元素从左至右比较一遍称为一趟交换，将待排序元素从左至右比较一遍称为一趟“冒泡冒泡”。每趟冒泡都将待排序列中的最大关键字交换到最后（或最前）每趟冒泡都将待排序列中的最大关键字交换到最后（或最前）位置。直到全部元素有序为止。位置。直到全部元素有序为止。a1 a2 a3 an-1 an 最大值最大值2.冒泡排序算法nstep1 从待排序队列的前端开始从待排序队列的前端开始(a1)两两比较记录两两比较记录的关键字值，若的关键字值，若aiai+1(i=1,2,n-1)，则交换，则交换ai和和ai+1的位置，直到队
7、列尾部。一趟冒泡处理，将序的位置，直到队列尾部。一趟冒泡处理，将序列中的最大值交换到列中的最大值交换到an的位置。的位置。nstep2 如法炮制，第如法炮制，第k趟冒泡，从待排序队列的前趟冒泡，从待排序队列的前端开始端开始(a1)两两比较两两比较ai和和ai+1（i=1,2,n-k)，并进，并进行交换处理，选出序列中第行交换处理，选出序列中第k大的关键字值，放在大的关键字值，放在有序队列的最前端。有序队列的最前端。(思考：为什么思考：为什么i=1,n-k?)nStep3 最多执行最多执行n-1趟的冒泡处理，序列变为有序。趟的冒泡处理，序列变为有序。n从小到大排序从小到大排序冒泡排序算法举例设有
8、数列 65,97,76,13,27,49,58 比较次数 第1趟 65，76，13，27，49，58，97 6 第2趟 65，13，27，49，58，76，97 5 第3趟 13，27，49，58，65，76，97 4 第4趟 13，27，49，58，65，76，97 3 第5趟 13，27，49，58，65，76，97 2 第6趟 13，27，49，58，65，76，97 1 总计：21 次3.冒泡排序实现bubble(int*item,int count)int a,b，t;for(a=1;acount;a+)/*n-1趟冒泡处理*/for(b=1;bitemb)/*若逆序，则交换*/t=
9、itemb-1;/*它们的位置*/itemb-1=itemb;itemb=t;4.改进的冒泡排序n从上述举例中可以看出，从第从上述举例中可以看出，从第4趟冒泡起，序列已有序，趟冒泡起，序列已有序，结果是空跑了结果是空跑了3趟。趟。若两次冒泡处理过程中，没有进行交若两次冒泡处理过程中，没有进行交换，说明序列已有序换，说明序列已有序，则停止交换。，则停止交换。这就是改进的冒泡算这就是改进的冒泡算法的处理思想。法的处理思想。n用改进的冒泡算法进行处理，比较次数有所减少。用改进的冒泡算法进行处理，比较次数有所减少。对于数列对于数列 65,97,76,13,27,49,58 比较次数比较次数 第第1趟趟
10、 65，76，13，27，49，58，97 6 第第2趟趟 65，13，27，49，58，76，97 5 第第3趟趟 13，27，49，58，65，76，97 4 第第4趟趟 13，27，49，58，65，76，97 3 总计：总计：18 次次bubble_a(int*item,int count)int a,b,t,c;for(a=1;acount;+a)/*n-1趟的循环 */c=1;/*设置交换标志 */for(b=1;bitemb)/*若逆序，则*/t=itemb-1;/*交换位置 */itemb-1=itemb;itemb=t;c=0;/*若有交换，则 */*改变交换标志 */if(
11、c)break;/*若没有交换，则*/*退出处理 */5.算法评价v若待排序列有序若待排序列有序(递增或递减递增或递减)，则只需进，则只需进行一趟冒泡处理即可；若反序，则需进行行一趟冒泡处理即可；若反序，则需进行n-1趟的冒泡处理。在最坏的情况下，冒趟的冒泡处理。在最坏的情况下，冒泡算法的时间复杂度是泡算法的时间复杂度是O(n2)。v当待排序列基本有序时，采用冒泡排序法当待排序列基本有序时，采用冒泡排序法效果较好。效果较好。v冒泡排序算法是冒泡排序算法是稳定的稳定的。课堂练习n对下列数据进行冒泡排序对下列数据进行冒泡排序n23,34,69,21,5,66,7,8,12,34二、快速排序n快速排
12、序法是对冒泡排序法的一种改进，快速排序法是对冒泡排序法的一种改进，也是基于交换排序的一种算法。因此，也是基于交换排序的一种算法。因此，被称为被称为“分区交换排序分区交换排序”。n快 速 排 序 法 是 一 位 计 算 机 科 学 家快 速 排 序 法 是 一 位 计 算 机 科 学 家C.A.R.Hoare推出并命名的。曾被认为推出并命名的。曾被认为是最好的一种排序方法。是最好的一种排序方法。1.快速排序基本思想n在待排序序列中按某种方法选取一个元素在待排序序列中按某种方法选取一个元素K，以它为分界点，以它为分界点，用交换的方法将序列分为两个部分：比该值小的放在左边，用交换的方法将序列分为两个
13、部分：比该值小的放在左边，否则放在右边。形成否则放在右边。形成 左子序列左子序列K右子序列右子序列 再分别对左、右两部分实施上述分解过程，直到各子序列长再分别对左、右两部分实施上述分解过程，直到各子序列长度为度为1，即有序为止。，即有序为止。n分界点元素值分界点元素值K的选取方法不同，将构成不同的排序法，也的选取方法不同，将构成不同的排序法，也将影响排序的效率：将影响排序的效率：n取左边第1个元素为分界点；n取中点A（left+right）/2为分界点；n选取最大和最小值的平均值为分界点等。2.快速排序算法nStep1 分别从两端开始，指针i指向第一个元素Aleft，指针j指向最后一个元素Ar
14、ight，分界点取K；nStep2 循环（ij）n从左边开始进行比较：从左边开始进行比较：若若K AiK Ai，则，则 i=i+1i=i+1，再进行比较；，再进行比较；若若K K Ai Ai，则将，则将AiAi交换到右边。交换到右边。n从右边开始进行比较：从右边开始进行比较：若若K K Aj Aj，则将，则将AjAj交换到左边；交换到左边；若若K Aj K Aj，则，则 j=j-1j=j-1，再进行比较；，再进行比较；n当当i=ji=j时，一次分解操作完成。时，一次分解操作完成。nStep3 在对分解出的左、右两个子序列按上述步骤继续进行分解，直到子序列长度为1（不可再分）为止，也即序列全部有
15、序。qs(int*item,int left,int right)int i,j,x,y,k;i=left;j=right;x=item(left+right)/2;/*计算中点位置 */do /*ij 的循环处理 */while(itemix&iright)i+；/*确定i点交换位置 */while(xleft)j-;/*确定j点交换位置 */if(i=j)/*如果i、j位置合法，则交换*/y=itemi;/*Ai和Aj的位置 */itemi=itemj;itemj=y;i+;j-;while(i=j);if(leftj)qs(item,left,j);/*对分割出的左部处理*/if(iri
16、ght)qs(item,i,right);/*对分割出的右部处理*/快速排序算法举例快速排序算法举例对于数列49，38，60，90，70，15，30，49，采用中点分界法：初始状态:49 38 60 90 70 15 30 49 比较次数 第1趟 49 38 60 90 70 15 30 49 49 38 60 90 70 15 30 49 5（i4、j1）49 38 60 49 70 15 30 90 5（i4、j1）49 38 60 49 70 15 30 90 小计：10 ik=90jij ji快速排序算法举例（续一）初始状态初始状态:49 38 60 49 70 15 30 :49 3
17、8 60 49 70 15 30 比较次数比较次数 第第2 2趟趟 49 38 60 49 38 60 4949 70 15 30 70 15 30 2 2（i1i1、j1j1）30 38 60 30 38 60 4949 70 15 49 70 15 49 30 38 60 30 38 60 4949 70 15 49 70 15 49 30 38 15 49 70 60 49 30 38 15 49 70 60 49 30 38 15 30 38 15 49 49 70 60 49 70 60 49 小计：小计：8 8ijk=49jii3 3（i2i2、j1j1）j3 3（i1i1、j2j
18、2）快速排序算法举例（续二）初始状态初始状态:30 38 15 :30 38 15 比较次数比较次数 第第3 3趟趟 30 38 15 330 38 15 3（i2i2、j1j1）30 30，15 38 15 38 小计：小计：3 3 第第4 4趟趟 70 60 49 270 60 49 2（i1i1、j1j1）49 60 70 249 60 70 2（i1i1、j1j1）小计：小计：4 4k=38ijk=60ji快速排序算法举例（续三）初始状态初始状态:30 15 :30 15 比较次数比较次数 第第5 5趟趟 30 15 230 15 2（i1i1、j1j1）15 30 15 30 小计：
19、小计：2 2 最后状态：最后状态：15 30 38 49 49 60 70 90 15 30 38 49 49 60 70 90 总计：总计：27 27 k=30ij课堂练习nP233 3.9数据（数据（2）4.算法评价v分界点选取方法不同，排序效果差异很大；分界点选取方法不同，排序效果差异很大；v比较次数为比较次数为nlogn，即为：，即为：O（nlogn）。）。v快速排序算法是快速排序算法是不稳定的不稳定的。三、简单插入排序1.1.基本思想：基本思想：n将将n n个元素的数列分为已有序和无序两个部分。个元素的数列分为已有序和无序两个部分。a1，a2，a3，a4，,an a1(1)，a2(1
20、)，a3(1)，a4(1),an(1).a1(n-1)，a2(n-1)，,an(n-1)有序有序 无序无序n每次处理：将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较,找出插入位置,将该元素插入到有序数列的合适位置中。n从前往后，若比ai小，则放在ai前面n从后往前，若比ai大，则放在ai后边。2.插入排序算法步骤nStep1 从有序数列从有序数列a1和无序数列和无序数列a2,a3,an开开始进行排序始进行排序;nStep2 处理第处理第i个元素时个元素时(i=2,3,n),数列数列 a1,a2,ai-1是已有序的是已有序的,而数列而数列ai,ai+1,an是无是无序的。用序的。用a
21、i与与ai-1、a i-2,a1进行比较进行比较,找出合适找出合适的位置将的位置将ai插入。（从后往前比较）插入。（从后往前比较）nStep3 重复重复Step2，共进行，共进行n-1的插入处理，数列的插入处理，数列全部有序。（从小到大排序）全部有序。（从小到大排序）插入排序举例 设有数列设有数列 18 18，1212，1010，1212，3030，16 16 初始状态：初始状态：1818，1212，1010，1212，3030，16 16 比较次数比较次数 i=1 18i=1 18，1212，1010，1212，3030，16 116 1 i=2 i=2 1212，1818，1010，121
22、2，3030，16 216 2 i=3 i=3 1010，1212，1818，1212，3030，16 216 2 i=4 i=4 1010，1212，1212，1818，3030，16 116 1 i=5 i=5 1010，1212，1212，1818，3030，16 3 16 3 1010，1212，1212，1616，1818，30 30 总计：总计：9 9 次次插入排序算法实现 insert_sort(item,n)int*item，n；int i，j，t；for（i=1；i=0&t ai+1，则交换它们的位置。，则交换它们的位置。nStep3 重复上述步骤，直到重复上述步骤，直到dK
23、=1。希尔排序例子d=5d=3插入排序插入排序最后以最后以1步长进行排序步长进行排序（此时就是简单的插入排序了）（此时就是简单的插入排序了）n希尔排序是基于插入排序的以下两点性希尔排序是基于插入排序的以下两点性质而提出改进方法的：质而提出改进方法的：1）插入排序在对几乎已经排好序的数据操）插入排序在对几乎已经排好序的数据操作时，作时，效率高，效率高，即可以达到线性排序的即可以达到线性排序的效率；效率；2）但插入排序一般来说是低效的，）但插入排序一般来说是低效的，因为因为插入排序每次只能将数据移动一位。插入排序每次只能将数据移动一位。3.SHELL排序算法(c+语言)template shell
24、sort(T item,int n)int i,j,h;T t;h=n/2；while(h0)for(i=h;in;i+)/内部为插入排序 t=itemi;j=i-h;while(t=0)itemj+h=itemj;j=j-h;itemj+h=t;h=h/2；4.算法评价n希尔排序算法比较次数约为希尔排序算法比较次数约为n1.5，因此，因此，其时间复杂度为其时间复杂度为O（n1.5）。）。n该算法是该算法是不稳定的不稳定的。希尔排序课堂练习n23 33 21 1 24 14 2 26 90 43nd=5 3 1五、简单选择排序n1.1.基本思想：基本思想：每次从待排序的记录中选出每次从待排序的
25、记录中选出关键字最小（或最大）的记录，顺序放在关键字最小（或最大）的记录，顺序放在已有序的记录序列的最后（或最前）面，已有序的记录序列的最后（或最前）面，直到全部数列有序。直到全部数列有序。a1，a2，a3，a4，,an a1(1)，a2(1)，a3(1)，a4(1),an(1).a1(n-1)，a2(n-1)，,an(n-1)有序有序 无序无序2.选择排序算法步骤nStep1 从原始数列从原始数列a1,a2,a3,an开始进行排开始进行排序，比较序，比较n-1次，从中选出最小关键字，放次，从中选出最小关键字，放在有序数列中，形成在有序数列中，形成a1、a2,a3,an有序有序数列和无序数列两
26、部分，完成第数列和无序数列两部分，完成第1趟排序。趟排序。nStep2 处理第处理第i趟排序时趟排序时(i=2,3,n)，从剩下，从剩下的的n-i+1个元素中找出最小关键字，放在有个元素中找出最小关键字，放在有序数列的后面。序数列的后面。nStep3 重复重复Step2，共进行，共进行n-1趟的选择处理，趟的选择处理，数列全部有序。数列全部有序。选择排序举例 设有数列设有数列 18 18，1212，1010，1212，3030，16 16 初始状态：初始状态：，1818，1212，1010，1212，3030，16 16 比较次数比较次数 i=1 i=1 1010，1818，1212，1212
27、，3030，16 516 5 i=2 i=2 1010，1212，1818，1212，3030，16 416 4 i=3 i=3 1010，1212，1212，1818，3030，16 316 3 i=4 i=4 1010，1212，1212，1616，1818，30 230 2 i=5 i=5 1010，1212，1212，1616，1818，30 1 30 1 总计：总计：15 15 次次3.选择排序算法select_sort(int*item,int count)int i,j,k,t;for(i=0;icount-1;+i)/n-1次循环 k=i;/无序部分第1个元素 t=itemi;
28、/及位置 for(j=i+1;jcount;+j)/寻找最小值循环 if(itemj=low(n/2)i=low(n/2)的结的结点都是叶子，因此以这些结点为根的子树都已是堆。点都是叶子，因此以这些结点为根的子树都已是堆。（1）建堆次序1313一个结点的树是堆一个结点的树是堆05052323919124241616888842421313建大根堆建大根堆(c)(c)只需依次将序号为只需依次将序号为low(n/2)low(n/2)-1low(n/2)low(n/2)-1，.，1 1的结点作为根的子树都调整为堆即可。的结点作为根的子树都调整为堆即可。232391912424161605058888
29、42421313n/2n/2（1）建堆次序(2)建堆方法-“筛选法”一:如果Ri的左右子树已是堆，这两棵子树的根分别是各自子树中关键字最大的结点。23239191242416160505888842421313二二:若根的关键字已是三者（根、左孩子、右孩子）若根的关键字已是三者（根、左孩子、右孩子）中的最大者，则无须做任何调整；中的最大者，则无须做任何调整；否则否则必须将具必须将具有有最大关键字的最大关键字的孩子与根交换。孩子与根交换。23239191242416160505888842421313三:交换之后有可能导致新子树不再是堆，需要将新子树调整为堆。如此逐层递推下去，直到调整到树叶为止
30、。42428888919113132424161605052323424288889191131324241616050523231717,1414思考:如果最后一个节点不是14，而是12将如何？例子：例子：关键字序列为关键字序列为 4242，1313，9191，2323，2424，1616，0505，8888，n=8n=8，故从第四个结点开始调整，故从第四个结点开始调整424213139191232324241616050588884213912324160588424213139191888824241616050523234213918824160523不调整不调整42421313919
31、1888824241616050523234213918824160523424288889191232324241616050513134288912324160513919188884242232324241616050513139188422324160513建成的堆建成的堆424213139191888824241616050523234213918824160523m=2m=2hm=t=13hm=t=13j=4 hj=88 j=4 hj=88 hj+1=24hj+1=24j jm mSIFT(ET h,int n;int m)SIFT(ET h,int n;int m)int j;E
32、T t;t=hm;int j;ET t;t=hm;j=2 j=2*m;m;while(j=n)/while(j=n)/处理到叶子处理到叶子 if(jn)&(hj hj+1)if(jn)&(hj hj+1)j+;/j+;/两颗子树比较两颗子树比较 if(thj)/exchangeif(thj)/exchange hm=hj;hm=hj;hj=t hj=t m=j;m=j;j=2 j=2*m;m;else break;else break;SIFT(ET h,int n;int m)SIFT(ET h,int n;int m)int j;ET t;t=hm;int j;ET t;t=hm;j=2
33、j=2*m;m;while(j=n)/while(j=n)/处理到叶子处理到叶子 if(jn)&(hj hj+1)if(jn)&(hj hj+1)j+;/j+;/两颗子树比较两颗子树比较 if(thj)/exchangeif(thj)/exchange hm=hj;hm=hj;hj=t hj=t m=j;m=j;j=2 j=2*m;m;else break;else break;42429191888824241616050523234288918824160523m=4 t=13m=4 t=13hm=13hm=13j=8 hj=23j=8 hj=23 hn+1=0hn+1=01313j jm
34、 mSIFT(ET h,int n;int m)SIFT(ET h,int n;int m)int j;ET t;t=hm;int j;ET t;t=hm;j=2 j=2*m;m;while(j=n)/while(j=n)/处理到叶子处理到叶子 if(jn)&(hj hj+1)if(jn)&(hj hj+1)j+;/j+;/两颗子树比较两颗子树比较 if(thj)/exchangeif(t=0;i-)SIFT(R,n-1,i)q 由于建堆的结果把关键字最大的记录选到了堆顶的位置，由于建堆的结果把关键字最大的记录选到了堆顶的位置，而排序的结果应是升序，如何解决而排序的结果应是升序，如何解决?3.
35、堆排序算法q应该将应该将R0R0和和Rn-1Rn-1交换，这就得到了第一趟排序的结交换，这就得到了第一趟排序的结果。果。q 第二趟排序的操作首先是将无序区第二趟排序的操作首先是将无序区R0R0到到Rn-2Rn-2调整调整为堆。这时对于当前堆来说，它的左右子树仍然是堆，为堆。这时对于当前堆来说，它的左右子树仍然是堆，所以，可以调用所以，可以调用SIFTSIFT函数将函数将R0R0到到Rn-2Rn-2调整为大根堆，调整为大根堆，选出最大关键字放入堆顶，然后将堆顶与当前无序区的选出最大关键字放入堆顶，然后将堆顶与当前无序区的最后一个记录最后一个记录Rn-2Rn-2交换，如此反复进行下去。交换，如此反
36、复进行下去。919188884242232324241616050513139188422324160513（a a）初始堆）初始堆R1R1到到R8R8举例：举例：131388884242232324241616050591911388422324160591（b b）第一趟排序之后）第一趟排序之后（c c）重建的堆）重建的堆R1R1到到R7R7888824244242232313131616050591918824422313160591050524244242232313131616888891910524422313168891（d d）第二趟排序之后）第二趟排序之后（e e）重建的堆）
37、重建的堆R1R1到到R6R6424224241616232313130505888891914224162313058891（f f）第三趟排序之后）第三趟排序之后050524241616232313134242888891910524162313428891（g g）重建的堆）重建的堆R1R1到到R5R5242423231616050513134242888891912423160513428891（h h）第四趟排序之后）第四趟排序之后131323231616050524244242888891911323160524428891（i i）重建的堆）重建的堆R1R1到到R4R4232313
38、131616050524244242888891912313160524428891（j j）第五趟排序之后）第五趟排序之后050513131616232324244242888891910513162324428891（k k）重建的堆）重建的堆R1R1到到R3R3161613130505232324244242888891911613052324428891（l l）第六趟排序之后）第六趟排序之后050513131616232324244242888891910513162324428891（m m）重建的堆）重建的堆R1R1到到R2R213130505161623232424424288
39、8891911305162324428891（n n）第七趟排序之后）第七趟排序之后050513131616232324244242888891910513162324428891HEAPSORT(ET p)HEAPSORT(ET p)int i;ET t;int i;ET t;for(i=n/2-1;i=1;i-)for(i=n/2-1;i=1;i-)sift(p,n-1,i);sift(p,n-1,i);for(i=n-1;i=1;i-)for(i=n-1;i=1;i-)t=p0;p0=pi;t=p0;p0=pi;pi=t;pi=t;sift(p,i-1,0);sift(p,i-1,0);
40、4.堆排序的时间复杂度堆排序的时间复杂性为O(nlog2n)空间复杂性为 O(1)堆排序是不稳定的排序方法。堆排序课堂练习n23 33 21 1 24 14 2 26 90 43n1）先建大根堆（写出过程）先建大根堆（写出过程）n2）排序！）排序！n若将两个有序表合并成一个有序表，称为若将两个有序表合并成一个有序表，称为2-2-路路归并。归并。l25 57 48 37 12 92 86 25 57 37 48 12 92 86 25 37 48 57 12 86 92 12 25 37 48 57 86 92 归并排序就是利用上述归并操作实现排序的。归并排序就是利用上述归并操作实现排序的。(1
41、)(1)将待排序列将待排序列R1R1到到RnRn看成看成n n个长度为个长度为1 1的有序子序的有序子序列，把这些子序列两两归并，便得到列，把这些子序列两两归并，便得到high(n/2)high(n/2)个有序个有序的子序列。的子序列。(2)(2)然后再把这然后再把这high(n/2)high(n/2)个有序的子序列两两归并，个有序的子序列两两归并，如此反复，直到最后得到一个长度为如此反复，直到最后得到一个长度为n n的有序序列。的有序序列。(3)(3)上述每次归并操作，都是将两个子序列归并为一个上述每次归并操作，都是将两个子序列归并为一个子序列，这就是子序列，这就是“二路归并二路归并”，类似
42、地还可以有，类似地还可以有“三三路归并路归并”或或“多路归并多路归并”。算法评价n空间复杂度为空间复杂度为O O（n n），），用辅助空间用辅助空间L1L1、L2L2、（、（SwapSwap）n时间复杂度为时间复杂度为O O（nlognnlogn）n2-2-路归并排序算法是路归并排序算法是稳定的稳定的。八、基数排序 q多关键字排序技术：多关键字（多关键字排序技术：多关键字（K K1 1,K,K2 2,K Kt t）;例如：关键字例如：关键字 K K1 1 小的结点排在前面。如关键字小的结点排在前面。如关键字 K K1 1相同，则比较关键字相同，则比较关键字 K K2 2 ，关键字，关键字 K
43、K2 2 小的结点排在小的结点排在前面，依次类推前面，依次类推 1.举例p 假定给定的是假定给定的是 t=2 位十进制数，存放在数组位十进制数，存放在数组 B 之中。之中。现要求通过基数排序法将其排序。现要求通过基数排序法将其排序。p 设置十个口袋，因十进制数分别有数字：设置十个口袋，因十进制数分别有数字：0，1，2，9，分别用，分别用 B0、B1、B2、B9 进行标识。进行标识。p 执行执行 j=1t(这里这里t=2)次循环，每次进行一次分配次循环，每次进行一次分配动作，一次收集动作。动作，一次收集动作。p 将右起第将右起第 j 位数字相同的数放入同一口袋。比如数字位数字相同的数放入同一口袋
44、。比如数字为为 1 者，则放入口袋者，则放入口袋B1，余类推余类推 收集：按收集：按 B0、B1、B2、B9 的顺序进行收集。的顺序进行收集。基数排序举例 e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。B=5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。袋。基数排序举例 e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。B=5、2、9、7、18、17、52 B0B1B2B3
45、B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。袋。5基数排序举例 e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。B=5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。袋。5基数排序举例 e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。B=5、2、9、7、18、17、52 B0B1B2
46、B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。袋。52基数排序举例 e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。B=5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。袋。52基数排序举例 e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。B=5、2、9、7、18、17、52 B0
47、B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。袋。529基数排序举例 e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。B=5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。袋。529基数排序举例 e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。B=5、2、9、7、18、17
48、、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。袋。5297基数排序举例 e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。B=5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。袋。5297基数排序举例 e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。B=5、2、9
49、、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。袋。529718基数排序举例 e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。B=5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。袋。529718基数排序举例 e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法
50、进行排序。B=5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。袋。52971817基数排序举例 e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。B=5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。袋。52971817基数排序举例 e.g:B=5、2、9、7、18、17、52 用
