《基本排序技术6h》由会员分享，可在线阅读，更多相关《基本排序技术6h（129页珍藏版）》请在金锄头文库上搜索。
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年就已经被研究。虽然大部分人年就已经被研究。虽然大部分人认为这是一个已经被解决的问题，有用认为这是一个已经被解决的问题，有用的新算法仍在不断的被发明。（例子：的新算法仍在不断的被发明。（例子：图书馆排序图书馆排序在在20
3、04年被发表）年被发表）算法稳定性21212525494925*25*161608080 1 2 3 4 5494908081616ExchangExchang=1=125*25*25252121494908081616ExchangExchang=1=125252525* *2121算法稳定性算法稳定性n当相等的元素是无法分辨的，比如像是整数，当相等的元素是无法分辨的，比如像是整数，稳定性并不是一个问题。然而，假设以下的数稳定性并不是一个问题。然而，假设以下的数对将要以他们的第一个数字来排序。对将要以他们的第一个数字来排序。n(4, 1) (3, 1) (3, 7) (5, 6)n(3, 1
4、) (3, 7) (4, 1) (5, 6) (保持保持次序次序) n(3, 7) (3, 1) (4, 1) (5, 6) (次序被次序被改变改变)n不稳定排序算法可能会在相等的键值中改变纪不稳定排序算法可能会在相等的键值中改变纪录的相对次序。录的相对次序。n不稳定排序算法可以被特别地实现为稳定。方不稳定排序算法可以被特别地实现为稳定。方法是法是 人工扩充键值的比较。然而，要记住这种人工扩充键值的比较。然而，要记住这种次序通常牵次序通常牵 涉到额外的空间负担。涉到额外的空间负担。n简单起见，这里用顺序存储结构描述待排简单起见，这里用顺序存储结构描述待排序的记录。序的记录。n顺序存储结构（顺序
5、存储结构（C语言描述）：语言描述）： #define N n typedef struct record int key ； /* 关键字项 */ int otherterm； /* 其它项其它项 */ ； typedef struct record RECORD； RECORD fileN+1；/*RECORD型的型的N+1元数组元数组*/排序算法的数据结构典型排序算法n冒泡排序冒泡排序n快速排序快速排序n简单插入排序简单插入排序n希尔排序希尔排序n简单选择排序简单选择排序n堆排序堆排序n归并排序归并排序n基数排序基数排序n二叉排序树二叉排序树一、冒泡排序n1.指导思想：指导思想： 两两两两
6、比比较较待待排排序序记记录录的的关关键键字字，并并交交换换不不满满足足顺顺序序要要求求的的那那些偶对元素，直到全部数列满足有序为止。些偶对元素，直到全部数列满足有序为止。n冒冒泡泡排排序序（Bubble sort）是是基基于于交交换换排排序序的的一一种种算算法法。它它是是依依次次两两两两比比较较待待排排序序元元素素；若若为为逆逆序序（递递增增或或递递减减）则则进进行行交交换换，将将待待排排序序元元素素从从左左至至右右比比较较一一遍遍称称为为一一趟趟“冒冒泡泡”。每每趟趟冒冒泡泡都都将将待待排排序序列列中中的的最最大大关关键键字字交交换换到到最最后后（或或最最前前）位置。直到全部元素有序为止。位
7、置。直到全部元素有序为止。 a1 a2 a3 an-1 an 最大值最大值2.冒泡排序算法nstep1 从待排序队列的前端开始从待排序队列的前端开始(a1)两两比较记录两两比较记录的关键字值，若的关键字值，若aiai+1(i=1,2,n-1)，则交换，则交换ai和和ai+1的位置，直到队列尾部。一趟冒泡处理，将序的位置，直到队列尾部。一趟冒泡处理，将序列中的最大值交换到列中的最大值交换到an的位置。的位置。nstep2 如法炮制，第如法炮制，第k趟冒泡，从待排序队列的前趟冒泡，从待排序队列的前端开始端开始(a1)两两比较两两比较ai和和ai+1（i=1 , 2 , n-k)，并进，并进行交换处
8、理，选出序列中第行交换处理，选出序列中第k大的关键字值，放在大的关键字值，放在有序队列的最前端。有序队列的最前端。(思考：为什么思考：为什么i=1,n-k?)nStep3 最多执行最多执行n-1趟的冒泡处理，序列变为有序。趟的冒泡处理，序列变为有序。n从小到大排序从小到大排序冒泡排序算法举例设有数列 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
9、，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=itemb-1; /* 它们的位置 */ itemb-1=itemb; itemb=t; 4.改进的冒泡排序n从从上上述述举举例例中中可可以以看看出出，从从第第4趟趟冒冒泡泡起起，序序列列已已有有序序，结结果果是是空空跑跑了了3趟趟。若若两两次次冒冒泡泡处处理理过过程程中中，没没有有进进
10、行行交交换换，说说明明序序列列已已有有序序，则则停停止止交交换换。这这就就是是改改进进的的冒冒泡泡算算法的处理思想。法的处理思想。n用改进的冒泡算法进行处理，比较次数有所减少。用改进的冒泡算法进行处理，比较次数有所减少。 对于数列对于数列 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 总计：总计： 18 次次bubble_a(int *item,int
11、 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(c) break; /* 若没有交换，则 */ /* 退出处理 */ 5. 算法评价v若待排序列有序若待排序列有序(递增或递减递增或递减)，则只需进，则只需进行一趟冒泡处理即可；若反序，则需进行行一趟冒泡处理即可；若反序，则需进行n-1趟的冒
12、泡处理。在最坏的情况下，冒泡趟的冒泡处理。在最坏的情况下，冒泡算法的时间复杂度是算法的时间复杂度是O( n2 )。v当待排序列基本有序时，采用冒泡排序法当待排序列基本有序时，采用冒泡排序法效果较好。效果较好。v冒泡排序算法是冒泡排序算法是稳定的稳定的。 课堂练习n对下列数据进行冒泡排序对下列数据进行冒泡排序n23 ,34,69,21,5,66,7,8,12,34二、快速排序n快快速速排排序序法法是是对对冒冒泡泡排排序序法法的的一一种种改改进进，也也是是基基于于交交换换排排序序的的一一种种算算法法。因因此此，被称为被称为“分区交换排序分区交换排序”。n快快速速排排序序法法是是一一位位计计算算机机
13、科科学学家家推推出出并并命命名名的的。曾曾被被认认为为是是最最好好的的一一种种排排序序方方法。法。1.快速排序基本思想n在在待待排排序序序序列列中中按按某某种种方方法法选选取取一一个个元元素素K，以以它它为为分分界界点点，用用交交换换的的方方法法将将序序列列分分为为两两个个部部分分：比比该该值值小小的的放放在在左左边边，否则放在右边。形成否则放在右边。形成 左子序列左子序列K右子序列右子序列 再再分分别别对对左左、右右两两部部分分实实施施上上述述分分解解过过程程，直直到到各各子子序序列列长长度为度为1，即有序为止。，即有序为止。n分分界界点点元元素素值值K的的选选取取方方法法不不同同，将将构构
14、成成不不同同的的排排序序法法，也也将影响排序的效率：将影响排序的效率：n取左边第1个元素为分界点；n取中点A（left+right）/2为分界点；n选取最大和最小值的平均值为分界点等。2. 快速排序算法nStep1 分别从两端开始，指针i指向第一个元素Aleft，指针j指向最后一个元素Aright，分界点取K；nStep2 循环（ij）n从左边开始进行比较：从左边开始进行比较： 若若K AiK Ai，则，则 i=i+1i=i+1，再进行比较；，再进行比较； 若若K K Ai Ai，则将，则将AiAi交换到右边。交换到右边。n从右边开始进行比较：从右边开始进行比较： 若若K K Aj Aj，则将
15、，则将AjAj交换到左边；交换到左边； 若若K Aj K Aj ，则，则 j=j-1j=j-1，再进行比较；，再进行比较；n当当i=ji=j时，一次分解操作完成。时，一次分解操作完成。nStep3 在对分解出的左、右两个子序列按上述步骤继续进行分解，直到子序列长度为1（不可再分）为止，也即序列全部有序。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+ ； /
16、* 确定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(iright) qs(item,i,right); /*对分割出的右部处理*/ 快速排序算法举例快速排序算法举例对于数列49，38，60，90，70，15，30，49，采用中点分界法：初始状态: 49 38 60 90 70 15
17、 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 38 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
18、 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、j2j2）快速排序算法举例（续二） 初始状态初始状态: 30 38 15 : 30 38 15 比较次数比较次数 第第3 3趟趟 30 38 15 330 38 15 3（i2i2、j1j1） 30 3
19、0， 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 小计：小计：2 2 最后状态：最后状态： 15 30 38 49 49 60 70 90 15 30 38 49 49 60 70 90 总计：总计： 27 27 k =
20、30ij课堂练习数据（数据（2）4. 算法评价v分界点选取方法不同，排序效果差异很大；分界点选取方法不同，排序效果差异很大；v比较次数为比较次数为nlogn，即为：，即为：O（nlogn）。）。v快速排序算法是快速排序算法是不稳定的不稳定的。 三、简单插入排序1.1.基本思想：基本思想：n将将n n个元素的数列分为已有序和无序两个部分。个元素的数列分为已有序和无序两个部分。 a1，a2，a3，a4，,an a1(1)，a2(1)，a3(1)，a4(1) ,an(1) . a1(n-1)，a2(n-1) ，, an(n-1)有序有序 无序无序n每次处理：将无序数列的第一个元素与有序数列的元素从后
21、往前逐个进行比较,找出插入位置,将该元素插入到有序数列的合适位置中。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是是无无序序的的。用用ai与与ai-1、a i-2,a1进进行行比比较较,找找出出合合适适的的位置将位置将ai插入。（从后往前比较）插入。（从后往前比较）nStep3 重重复复Step2
22、，共共进进行行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，1212，3030，16 216 2 i=3 i=3 1010，1212，1818 ，1212，3030，16 216 2 i=4 i=4 1010，1212，1212，
23、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 = 1。希尔排序例子d=5d=3插入排序插入排序最后以最后以1步长进行排序步长进行排序（此时就是简单的插入排序了）（此时就是简单
24、的插入排序了） n希尔排序是基于插入排序的以下两点性希尔排序是基于插入排序的以下两点性质而提出改进方法的：质而提出改进方法的：1）插入排序在对几乎已经排好序的数据操）插入排序在对几乎已经排好序的数据操作时，作时， 效率高，效率高， 即可以达到线性排序的即可以达到线性排序的效率；效率； 2）但插入排序一般来说是低效的，）但插入排序一般来说是低效的， 因为因为插入排序每次只能将数据移动一位。插入排序每次只能将数据移动一位。 3. SHELL排序算法(c+语言)template shellsort(T item,int n) int i,j,h; T t; h=n/2 ； while(h0) for
25、(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希尔排序算法比较次数约为希尔排序算法比较次数约为n，因此，其，因此，其时间复杂度为时间复杂度为O（ n ）。）。n该算法是该算法是不稳定的不稳定的。希尔排序课堂练习n23 33 21 1 24 14 2 26 90 43nd=5 3 1五、简单选择排序n1.1.基基本本思思想想：每每次次从从待待排排序序的的记记录录中中选选出出关关键键字字最最小小（或或最最大大）的的记记录录，顺顺序序放放在在已已有有序序的
26、的记记录录序序列列的的最最后后（或或最最前前）面面，直到全部数列有序。直到全部数列有序。 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有有序序数列和无序数列两部分，完成第数列和无序数列两部分，完成第1趟排序。趟排序。nStep2 处处理理第第i趟趟排排序序
27、时时(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，3030，16 516 5 i=2 i=2 1010，1212 ，1818，1212，3030，16
28、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; / 及位置 for(j=i+1;jcount;+j) / 寻找最小值循环
29、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的结点作为根的子树都调整为堆即可。的结点作为根的子树都调整为堆即可。23239191242416160505888842421313n/2n/2（1） 建堆次序(2)
30、 建堆方法-“筛选法” 一: 如果Ri的左右子树已是堆，这两棵子树的根分别是各自子树中关键字最大的结点。23239191242416160505888842421313二二: :若根的关键字已是三者（根、左孩子、右孩子）若根的关键字已是三者（根、左孩子、右孩子）中的最大者，则无须做任何调整；中的最大者，则无须做任何调整；否则否则必须将具必须将具有有最大关键字的最大关键字的孩子与根交换。孩子与根交换。23239191242416160505888842421313三: 交换之后有可能导致新子树不再是堆， 需要将新子树调整为堆。如此逐层递推下去，直到调整到树叶为止。4242888891911313
31、2424161605052323424288889191131324241616050523231717 , ,1414思考:如果最后一个节点不是14，而是12将如何？例子：例子：关键字序列为关键字序列为 4242，1313，9191，2323， 2424， 1616，0505，8888，n=8n=8，故从第四个结点开始，故从第四个结点开始调整调整424213139191232324241616050588884213912324160588424213139191888824241616050523234213918824160523不调整不调整42421313919188882424161
32、6050523234213918824160523424288889191232324241616050513134288912324160513919188884242232324241616050513139188422324160513建成的堆建成的堆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
33、m) int j; ET t; t=hm; int j; ET t; t=hm; j=2 * m; j=2 * 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 * m;j=2 * m; else break; else break; SIFT(ET h, int n; int m) SI
34、FT(ET h, int n; int m) int j; ET t; t=hm; int j; ET t; t=hm; j=2 * m; j=2 * 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 * m;j=2 * m; else break; else break; 4242919
35、1888824241616050523234288918824160523m = 4 m = 4 t = 13t = 13hm = 13hm = 13j= 8 hj=23j= 8 hj=23 hn+1 =0hn+1 =01313j jm 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 * m; j=2 * m; while (j=n) /while (j=n) /处理到叶子处理到叶子 if (jn)&(hj hj+1) if (jn)&(hj hj+1) j
36、+; / j+; /两颗子树比较两颗子树比较 if (thj) /exchangeif (t=0; i-) SIFT(R, n -1, i)q 由于建堆的结果把关键字最大的记录选到了堆顶的位由于建堆的结果把关键字最大的记录选到了堆顶的位置，而排序的结果应是升序，如何解决置，而排序的结果应是升序，如何解决? ?3.堆排序算法q应该将应该将R0R0和和Rn-1Rn-1交换，这就得到了第一趟排序的交换，这就得到了第一趟排序的结果。结果。q 第二趟排序的操作首先是将无序区第二趟排序的操作首先是将无序区R0R0到到Rn-2Rn-2调整调整为堆。这时对于当前堆来说，它的左右子树仍然是堆，为堆。这时对于当前
37、堆来说，它的左右子树仍然是堆，所以，可以调用所以，可以调用SIFTSIFT函数将函数将R0R0到到Rn-2Rn-2调整为大根堆，调整为大根堆，选出最大关键字放入堆顶，然后将堆顶与当前无序区的选出最大关键字放入堆顶，然后将堆顶与当前无序区的最后一个记录最后一个记录Rn-2Rn-2交换，如此反复进行下去。交换，如此反复进行下去。919188884242232324241616050513139188422324160513（a a）初始堆）初始堆R1R1到到R8R8举例：举例：131388884242232324241616050591911388422324160591（b b）第一趟排序之后）
38、第一趟排序之后（c c）重建的堆）重建的堆R1R1到到R7R7888824244242232313131616050591918824422313160591050524244242232313131616888891910524422313168891（d d）第二趟排序之后）第二趟排序之后（e e）重建的堆）重建的堆R1R1到到R6R6424224241616232313130505888891914224162313058891（f f）第三趟排序之后）第三趟排序之后050524241616232313134242888891910524162313428891（g g）重建的堆）重建的
39、堆R1R1到到R5R5242423231616050513134242888891912423160513428891（h h）第四趟排序之后）第四趟排序之后131323231616050524244242888891911323160524428891（i i）重建的堆）重建的堆R1R1到到R4R4232313131616050524244242888891912313160524428891（j j）第五趟排序之后）第五趟排序之后050513131616232324244242888891910513162324428891（k k）重建的堆）重建的堆R1R1到到R3R3161613130
40、505232324244242888891911613052324428891（l l）第六趟排序之后）第六趟排序之后050513131616232324244242888891910513162324428891（m m）重建的堆）重建的堆R1R1到到R2R2131305051616232324244242888891911305162324428891（n n）第七趟排序之后）第七趟排序之后050513131616232324244242888891910513162324428891HEAPSORT(ET p)HEAPSORT(ET p) int i; ET t; int i; ET t
41、; 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); 4.堆排序的时间复杂度堆排序的时间复杂性为O(nlog2n) 空间复杂性为 O(1)堆排序是不稳定的排序方法。堆排序课堂练习n23 33 21 1 24 14 2 26 90 43n1）先建大根堆（写出过程）先建大根堆（
42、写出过程）n2）排序！）排序！七、归并排序基本原理：通过对两个有序结点序列的合并来实现排序。所谓归并是指将若干个已排好序的部分合并成一个有序的部分。n若将两个有序表合并成一个有序表，称为若将两个有序表合并成一个有序表，称为2-2-路路归并。归并。1.两路归并的基本思想(1) 设有两个有序表设有两个有序表A和和B，对象个数分别为，对象个数分别为al和和bl，变量，变量i和和j分别是两表的当前指针。分别是两表的当前指针。(2) 设表设表C是归并后的新有序表，变量是归并后的新有序表，变量k是它的当是它的当前指针。前指针。(3) i和和j对对A和和B遍历时，遍历时，依次将关键字小的对象依次将关键字小的
43、对象放放到到C中，当中，当A或或B遍历结束时，将另一个表的剩余遍历结束时，将另一个表的剩余部分照抄到新表中。部分照抄到新表中。两路归并的示例两路归并的示例25 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)(1)将待排序列将待排序列R1R1到到RnRn看成看成n n个长度为个长度为1 1的有序子序的有序子序列，把这些子序列两两归并，便得到列，把这些子序列两两归并，便得到high(n/2)high
44、(n/2)个有序个有序的子序列。的子序列。(2)(2)然后再把这然后再把这high(n/2)high(n/2)个有序的子序列两两归并，个有序的子序列两两归并，如此反复，直到最后得到一个长度为如此反复，直到最后得到一个长度为n n的有序序列。的有序序列。(3)(3)上述每次归并操作，都是将两个子序列归并为一个上述每次归并操作，都是将两个子序列归并为一个子序列，这就是子序列，这就是“二路归并二路归并”，类似地还可以有，类似地还可以有“三三路归并路归并”或或“多路归并多路归并”。算法评价n空间复杂度为空间复杂度为O O（ n n ），）， 用辅助空间用辅助空间L1L1、L2L2、（、（SwapSwa
45、p）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 K2 2 小的结点排小的结点排在前面，依次类推在前面，依次类推 1.举例p 假定给定的是假定给定的是 t = 2 位十进制数，存放在数组位十进制数，存放在数组 B 之中。
46、之中。现要求通过基数排序法将其排序。现要求通过基数排序法将其排序。p 设置十个口袋，因十进制数分别有数字：设置十个口袋，因十进制数分别有数字：0，1，2，9 ，分别用，分别用 B0、B1、B2、B9 进行标识。进行标识。p 执行执行 j = 1t (这里这里t = 2 )次循环，每次进行一次分配次循环，每次进行一次分配动作，一次收集动作。动作，一次收集动作。p 将右起第将右起第 j 位数字相同的数放入同一口袋。比如数字位数字相同的数放入同一口袋。比如数字为为 1 者，则放入口袋者，则放入口袋B1，余类推余类推 收集：按收集：按 B0、B1、B2、 B9 的顺序进行收集。的顺序进行收集。基数排序
47、举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。袋。基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。
48、袋。5基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。袋。5基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配
49、到相应的口 袋。袋。52基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。袋。52基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分
50、配到相应的口将其分配到相应的口 袋。袋。529基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。袋。529基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，
51、数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。袋。5297基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。袋。5297基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的
52、所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。袋。529718基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。袋。529718基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B
53、7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。袋。52971817基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。袋。52971817基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 5、2、9、7、18
54、、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。袋。5297181752基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋分配完毕，按照分配完毕，按照 箭头所指的方向进行箭头所指的方向进行 收集动作。注意：收收集动作。注意：收集后的序列已经按照集后的序列已经按照右起第一位（个位数右起第一位（个位数字）排好序了。字）排好序了。5297
55、181752收集后的序列：收集后的序列：2、52、5、7、17、18、9、基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 2、52、5、7、17、18、9 （第一次收集的结果）第一次收集的结果）B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。和第一次不同，袋。和第一次不同，这次根据右起第二位这次根据右起第二位数字（十位数字）进数字（十位数字）进分配。分配。基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序
56、法进行排序。用基数排序法进行排序。 B = 2、52、5、7、17、18、9 （第一次收集的结果）第一次收集的结果）B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。和第一次不同，袋。和第一次不同，这次根据右起第二位这次根据右起第二位数字（十位数字）进数字（十位数字）进分配。分配。2基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 2、52、5、7、17、18、9 （第一次收集的结果）第一次收集的结果）B0B1B2B3B4B5B
57、6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。和第一次不同，袋。和第一次不同，这次根据右起第二位这次根据右起第二位数字（十位数字）进数字（十位数字）进分配。分配。2基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 2、52、5、7、17、18、9 （第一次收集的结果）第一次收集的结果）B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。和第一次不同，
58、袋。和第一次不同，这次根据右起第二位这次根据右起第二位数字（十位数字）进数字（十位数字）进分配。分配。252基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 2、52、5、7、17、18、9 （第一次收集的结果）第一次收集的结果）B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。和第一次不同，袋。和第一次不同，这次根据右起第二位这次根据右起第二位数字（十位数字）进数字（十位数字）进分配。分配。252基数排序举例 : B = 5、
59、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 2、52、5、7、17、18、9 （第一次收集的结果）第一次收集的结果）B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。和第一次不同，袋。和第一次不同，这次根据右起第二位这次根据右起第二位数字（十位数字）进数字（十位数字）进分配。分配。2525基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 2、52、5、7、17、18、9 （第一次收集的结果
60、）第一次收集的结果）B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。和第一次不同，袋。和第一次不同，这次根据右起第二位这次根据右起第二位数字（十位数字）进数字（十位数字）进分配。分配。2525基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 2、52、5、7、17、18、9 （第一次收集的结果）第一次收集的结果）B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其
61、分配到相应的口将其分配到相应的口 袋。和第一次不同，袋。和第一次不同，这次根据右起第二位这次根据右起第二位数字（十位数字）进数字（十位数字）进分配。分配。25257基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 2、52、5、7、17、18、9 （第一次收集的结果）第一次收集的结果）B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。和第一次不同，袋。和第一次不同，这次根据右起第二位这次根据右起第二位数字（十位数字）进数字（十位
62、数字）进分配。分配。25257基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 2、52、5、7、17、18、9 （第一次收集的结果）第一次收集的结果）B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。和第一次不同，袋。和第一次不同，这次根据右起第二位这次根据右起第二位数字（十位数字）进数字（十位数字）进分配。分配。2525717基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排
63、序。 B = 2、52、5、7、17、18、9 （第一次收集的结果）第一次收集的结果）B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。和第一次不同，袋。和第一次不同，这次根据右起第二位这次根据右起第二位数字（十位数字）进数字（十位数字）进分配。分配。2525717基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 2、52、5、7、17、18、9 （第一次收集的结果）第一次收集的结果）B0B1B2B3B4B5B6B7B8B9口袋
64、口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。和第一次不同，袋。和第一次不同，这次根据右起第二位这次根据右起第二位数字（十位数字）进数字（十位数字）进分配。分配。252571718基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 2、52、5、7、17、18、9 （第一次收集的结果）第一次收集的结果）B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。和第一次不同，袋
65、。和第一次不同，这次根据右起第二位这次根据右起第二位数字（十位数字）进数字（十位数字）进分配。分配。252571718基数排序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 2、52、5、7、17、18、9 （第一次收集的结果）第一次收集的结果）B0B1B2B3B4B5B6B7B8B9口袋口袋根据根据 所指向的所指向的 数，进行分配动作，数，进行分配动作，将其分配到相应的口将其分配到相应的口 袋。和第一次不同，袋。和第一次不同，这次根据右起第二位这次根据右起第二位数字（十位数字）进数字（十位数字）进分配。分配。2525717189基数排
66、序举例 : B = 5、2、9、7、18、17、52 用基数排序法进行排序。用基数排序法进行排序。 B = 2、52、5、7、17、18、9 （第一次收集的结果）第一次收集的结果）B0B1B2B3B4B5B6B7B8B9口袋口袋2525717189分配完毕，按照分配完毕，按照箭头所指的方向进行箭头所指的方向进行 第二次收集动作。注第二次收集动作。注意：收集后的序列已意：收集后的序列已经按照右起第一位（经按照右起第一位（个位数字）、右起第个位数字）、右起第二位（十位数字）排二位（十位数字）排好序了。好序了。收集后的序列：收集后的序列：2、5、7、9、17、18、52已是排好序的序列。已是排好序的
67、序列。性能分析 空间：采用顺序分配，显然不合适。由于每个口袋都有可空间：采用顺序分配，显然不合适。由于每个口袋都有可能存放所有的待排序的整数。所以，额外空间的需求为能存放所有的待排序的整数。所以，额外空间的需求为 10n，太大了。，太大了。 采用链接分配是合理的。额外空间的需求为采用链接分配是合理的。额外空间的需求为 n，通常再增加指向每个口袋的首尾指针就可以了。在一般情况通常再增加指向每个口袋的首尾指针就可以了。在一般情况下，设每个键字的取值范围为下，设每个键字的取值范围为 rd, 首尾指针共计首尾指针共计 2rd 个个 ，总的空间为总的空间为 O( n+2rd) 。 时间：上例中每个数计有
68、时间：上例中每个数计有 t = 2 位，因此执行位，因此执行 t = 2 次分配次分配和收集就可以了。在一般情况下，每个结点有和收集就可以了。在一般情况下，每个结点有 d 位关键字，位关键字，必须执行必须执行 t = d次分配和收集操作。次分配和收集操作。 分配的代价：分配的代价：O(n) 收集的代价：收集的代价：O(rd) 总的代价为：总的代价为：O( d (n + rd)课堂练习n23,44,55,45,21,124,115,7,129,993.4 二叉排序树及其查找一、定义一、定义 所谓二叉排序树是指满足下列条件的二叉树：所谓二叉排序树是指满足下列条件的二叉树：（1 1）左子树上的所有结
69、点值均小于根结点值。）左子树上的所有结点值均小于根结点值。（2 2）右子树上的所有结点值均不小于根结点值。）右子树上的所有结点值均不小于根结点值。（3 3）左、右子树也满足上述两个条件）左、右子树也满足上述两个条件 二、 二叉排序树的特性v二叉排序树有一个二叉排序树有一个重要特性重要特性：中序遍历中序遍历二叉排序二叉排序树可以得到有序序列。因此，由无序序列构造二树可以得到有序序列。因此，由无序序列构造二叉排序树实际上就将一个无序序列变成了有序序叉排序树实际上就将一个无序序列变成了有序序列。列。v另外，由于在二叉排序树中插入的新结点都是叶另外，由于在二叉排序树中插入的新结点都是叶子结点，因此，在
70、对二叉排序树进行插入运算时，子结点，因此，在对二叉排序树进行插入运算时，不需移动其他结点，而只需改动插入位置上的叶不需移动其他结点，而只需改动插入位置上的叶子结点指针即可。子结点指针即可。 三、 二叉排序树的构造 依依次次读读入入给给定定序序列列中中的的每每一一个个元元素素，然然后后进进行行如如下下处理：处理： （1）若若当当前前的的二二叉叉排排序序树树为为空空，则则读读入入的的元元素素为为根根结点。结点。 （2）若读入的元素值小于根结点值，则将元素插入）若读入的元素值小于根结点值，则将元素插入到左子树中。到左子树中。 （3）若若读读入入的的元元素素值值不不小小于于根根结结点点值值，则则将将元
71、元素素插插入到右子树中。入到右子树中。 无论是插入到左子树还是右子树，都是同样按照上无论是插入到左子树还是右子树，都是同样按照上述方法处理。述方法处理。 四、 二叉排序树的删除 为为了了删删除除一一个个元元素素，首首先先要要找找到到被被删删除除元元素素所所在在的的结结点点p和它的父结点和它的父结点q，然后分以下，然后分以下3种情况进行处理：种情况进行处理： （1）p为叶子结点：直接删除，修改父结点指针。为叶子结点：直接删除，修改父结点指针。 （2）p为单支树：将为单支树：将P的子树链到的子树链到q上。上。 （3）p的的左左右右子子树树均均不不空空：将将p的的左左子子树树的的右右链链最最右右边边
72、的的结结点点s的的值值填填入入p中中，将将s的的左左链链链链到到s的的父父结结点点的右指针。的右指针。 五、二叉排序树查找算法算法描述:n输入一个值，在该树中查找，若找到输出该结点值；否则，显示查找失败。n与根比，相等，查找成功，n比根小，在左子树查n比根大，在右子树查n查左右子树时按同样的方法查 struct tree *search_btree(struct tree * root, char key) if (!root) cout info!=key) /* /* 查找key 的循环 * */ / if(keyinfo) root=root-left; /* /* 沿左路查找 * */ / else root=root-right; if(root=0) cout info!=key) */作业n（按下面要求进行排序）（按下面要求进行排序）n数据（数据（1）n1）快速排序）快速排序n2）希尔排序）希尔排序n3）使用堆排序）使用堆排序n写出中间步骤和结果写出中间步骤和结果
