基本排序技术6h.ppt

第三章查找与排序(下),本节内容,通过本单元的学习，了解、掌握有关排序的：基本概念：排序、排序分类、算法稳定性典型的排序算法:插入排序、选择排序、交换排序归并排序、基数排序,排序的基本概念,定义：将记录按关键字递增(递减)的次序排列起来，形成新的有序序列，称为排序。描述：设n个记录的序列为R1,R2,Rn,其相应关键字序列为K1,K2,Kn,需确定一种排序P1,P2,Pn,使其相应的关键字满足递增(升序),或递减(降序)的关系:Kp1 Kp2.Kpn 或 Kp1 Kp2.Kpn,3.3 基本的排序技术,虽然排序算法是一个简单的问题，但是从计算机科学发展以来，已经有大量的研究在此问题上。举例而言，冒泡排序在1956年就已经被研究。虽然大部分人认为这是一个已经被解决的问题，有用的新算法仍在不断的被发明。（例子：图书馆排序在2004年被发表）,算法稳定性,算法稳定性,当相等的元素是无法分辨的，比如像是整数，稳定性并不是一个问题。然而，假设以下的数对将要以他们的第一个数字来排序。(4,1)(3,1)(3,7)(5,6)(3,1)(3,7)(4,1)(5,6)(保持次序)(3,7)(3,1)(4,1)(5,6)(次序被改变),不稳定排序算法可能会在相等的键值中改变纪录的相对次序。不稳定排序算法可以被特别地实现为稳定。方法是 人工扩充键值的比较。然而，要记住这种次序通常牵 涉到额外的空间负担。,简单起见，这里用顺序存储结构描述待排序的记录。顺序存储结构（C语言描述）：#define N n typedef struct record int key；/*关键字项*/int otherterm；/*其它项*/；typedef struct record RECORD；RECORD fileN+1；/*RECORD型的N+1元数组*/,排序算法的数据结构,典型排序算法,冒泡排序快速排序简单插入排序希尔排序简单选择排序堆排序归并排序基数排序二叉排序树,一、冒泡排序,1.指导思想：两两比较待排序记录的关键字，并交换不满足顺序要求的那些偶对元素，直到全部数列满足有序为止。冒泡排序（Bubble sort）是基于交换排序的一种算法。它是依次两两比较待排序元素；若为逆序（递增或递减）则进行交换，将待排序元素从左至右比较一遍称为一趟“冒泡”。每趟冒泡都将待排序列中的最大关键字交换到最后（或最前）位置。直到全部元素有序为止。a1 a2 a3 an-1 an,2.冒泡排序算法,step1 从待排序队列的前端开始(a1)两两比较记录的关键字值，若aiai+1(i=1,2,n-1)，则交换ai和ai+1的位置，直到队列尾部。一趟冒泡处理，将序列中的最大值交换到an的位置。step2 如法炮制，第k趟冒泡，从待排序队列的前端开始(a1)两两比较ai和ai+1（i=1,2,n-k)，并进行交换处理，选出序列中第k大的关键字值，放在有序队列的最前端。(思考：为什么i=1,n-k?)Step3 最多执行n-1趟的冒泡处理，序列变为有序。从小到大排序,冒泡排序算法举例,设有数列 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;aitemb)/*若逆序，则交换*/t=itemb-1;/*它们的位置*/itemb-1=itemb;itemb=t;,4.改进的冒泡排序,从上述举例中可以看出，从第4趟冒泡起，序列已有序，结果是空跑了3趟。若两次冒泡处理过程中，没有进行交换，说明序列已有序，则停止交换。这就是改进的冒泡算法的处理思想。用改进的冒泡算法进行处理，比较次数有所减少。对于数列 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 count)int a,b,t,c;for(a=1;aitemb)/*若逆序，则*/t=itemb-1;/*交换位置*/itemb-1=itemb;itemb=t;c=0;/*若有交换，则*/*改变交换标志*/if(c)break;/*若没有交换，则*/*退出处理*/,5.算法评价,若待排序列有序(递增或递减)，则只需进行一趟冒泡处理即可；若反序，则需进行n-1趟的冒泡处理。在最坏的情况下，冒泡算法的时间复杂度是O(n2)。当待排序列基本有序时，采用冒泡排序法效果较好。冒泡排序算法是稳定的。,课堂练习,对下列数据进行冒泡排序23,34,69,21,5,66,7,8,12,34,二、快速排序,快速排序法是对冒泡排序法的一种改进，也是基于交换排序的一种算法。因此，被称为“分区交换排序”。快速排序法是一位计算机科学家推出并命名的。曾被认为是最好的一种排序方法。,1.快速排序基本思想,在待排序序列中按某种方法选取一个元素K，以它为分界点，用交换的方法将序列分为两个部分：比该值小的放在左边，否则放在右边。形成 左子序列K右子序列 再分别对左、右两部分实施上述分解过程，直到各子序列长度为1，即有序为止。分界点元素值K的选取方法不同，将构成不同的排序法，也将影响排序的效率：取左边第1个元素为分界点；取中点A（left+right）/2为分界点；选取最大和最小值的平均值为分界点等。,2.快速排序算法,Step1 分别从两端开始，指针i指向第一个元素Aleft，指针j指向最后一个元素Aright，分界点取K；Step2 循环（ij）从左边开始进行比较：若K Ai，则 i=i+1，再进行比较；若K Ai，则将Ai交换到右边。从右边开始进行比较：若K Aj，则将Aj交换到左边；若K Aj，则 j=j-1，再进行比较；当i=j时，一次分解操作完成。Step3 在对分解出的左、右两个子序列按上述步骤继续进行分解，直到子序列长度为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(itemileft)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 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,i,k=90,j,i,j,j,i,快速排序算法举例（续一）,初始状态:49 38 60 49 70 15 30 比较次数 第2趟 49 38 60 49 70 15 30 2（i1、j1）30 38 60 49 70 15 49 30 38 60 49 70 15 49 30 38 15 49 70 60 49 30 38 15 49 70 60 49 小计：8,i,j,k=49,j,i,i,3（i2、j1）,j,3（i1、j2）,快速排序算法举例（续二）,初始状态:30 38 15 比较次数 第3趟 30 38 15 3（i2、j1）30，15 38 小计：3 第4趟 70 60 49 2（i1、j1）49 60 70 2（i1、j1）小计：4,k=38,i,j,k=60,j,i,快速排序算法举例（续三）,初始状态:30 15 比较次数 第5趟 30 15 2（i1、j1）15 30 小计：2 最后状态：15 30 38 49 49 60 70 90 总计：27,k=30,i,j,课堂练习,P233 3.9数据（2）,4.算法评价,分界点选取方法不同，排序效果差异很大；比较次数为nlogn，即为：O（nlogn）。快速排序算法是不稳定的。,三、简单插入排序,1.基本思想：将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),有序 无序,每次处理：将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较,找出插入位置,将该元素插入到有序数列的合适位置中。从前往后，若比ai小，则放在ai前面从后往前，若比ai大，则放在ai后边。,2.插入排序算法步骤,Step1 从有序数列a1和无序数列a2,a3,an开始进行排序;Step2 处理第i个元素时(i=2,3,n),数列 a1,a2,ai-1是已有序的,而数列ai,ai+1,an是无序的。用ai与ai-1、a i-2,a1进行比较,找出合适的位置将ai插入。（从后往前比较）Step3 重复Step2，共进行n-1的插入处理，数列全部有序。（从小到大排序）,插入排序举例,设有数列 18，12，10，12，30，16 初始状态：18，12，10，12，30，16 比较次数 i=1 18，12，10，12，30，16 1 i=2 12，18，10，12，30，16 2 i=3 10，12，18，12，30，16 2 i=4 10，12，12，18，30，16 1 i=5 10，12，12，18，30，16 3 10，12，12，16，18，30 总计：9 次,插入排序算法实现,insert_sort(item,n)int*item，n；int i，j，t；for（i=1；i=0/插入该元素,4.算法评价,插入算法比较次数和交换次数约为 n2/2，因此，其时间复杂度为O（n2）。该算法是稳定的。,四.希尔（Shell）排序,1.思想：希尔排序是一种快速排序法，出自,指导思想：仍采用插入法，排序过程通过调换并移动数据项来实现。每次比较指定间距的两个数据项，若右边的值小于左边的值，则交换它们的位置。间距d按给定公式减少：di+1=（di+1）/2，直到d等于1为止。d取9，5，3，2，1。,2.算法步骤,Step1 将n个元素的数列分为m个部分，元素比较间距为d。Step2 在第i步，两元素比较的间距取 di+1=（di+1）/2 9，5，3，2，1 若 ai ai+1，则交换它们的位置。Step3 重复上述步骤，直到dK=1。,希尔排序例子,d=5,d=3,插入排序,最后以1步长进行排序（此时就是简单的插入排序了）,希尔排序是基于插入排序的以下两点性质而提出改进方法的：1）插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；2）但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。,3.SHELL排序算法(c+语言),template shellsort(T item,int n)int i,j,h;T t;h=n/2；while(h0)for(i=h;i=0)itemj+h=itemj;j=j-h;itemj+h=t;h=h/2；,4.算法评价,希尔排序算法比较次数约为n1.5，因此，其时间复杂度为O（n1.5）。该算法是不稳定的。,希尔排序课堂练习,23 33 21 1 24 14 2 26 90 43d=5 3 1,五、简单选择排序,1.基本思想：每次从待排序的记录中选出关键字最小（或最大）的记录，顺序放在已有序的记录序列的最后（或最前）面，直到全部数列有序。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.选择排序算法步骤,Step1 从原始数列a1,a2,a3,an开始进行排序，比较n-1次，从中选出最小关键字，放在有序数列中，形成a1、a2,a3,an有序数列和无序数列两部分，完成第1趟排序。Step2 处理第i趟排序时(i=2,3,n)，从剩下的n-i+1个元素中找出最小关键字，放在有序数列的后面。Step3 重复Step2，共进行n-1趟的选择处理，数列全部有序。,选择排序举例,设有数列 18，12，10，12，30，16 初始状态：，18，12，10，12，30，16 比较次数 i=1 10，18，12，12，30，16 5 i=2 10，12，18，12，30，16 4 i=3 10，12，12，18，30，16 3 i=4 10，12，12，16，18，30 2 i=5 10，12，12，16，18，30 1 总计：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)/寻找最小值循环 if(itemjt)k=j;t=itemj;/记录最小值及位置 itemk=itemi;/交换最小值与有序 itemi=t;/部分最后1个元素位置,4.算法评价,每次选出当前最小关键字，但没有为以后的选择留下任何信息，比较次数仍为 O（n2）。选择排序算法是不稳定的。,六、堆排序,堆排序是一种树型选择排序。在排序过程中，将R0到Rn-1看成是一个完全二叉树顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择关键字最小记录。堆排序分为两个步骤：1、根据初始输入，形成初始堆。2、通过一系列的对象交换和重新调整进行排序。,1.堆的定义,n个关键字序列K1,k2,.,Kn称为堆，当且仅当该序列满足特性：,从堆的定义可以看出，堆实质上是满足如下性质的二叉树：树中任一非叶子结点的关键字均小于或等于它的孩子结点的关键字。,10,15,56,25,30,70,10,15,56,25,30,70,小根堆示例,70,56,30,25,15,10,70,56,30,25,15,10,大根堆示例,*2.建堆,建堆的方法 次序 思想 举例实现算法,(a)只有一个结点的树是堆(b)而在完全二叉树中，所有序号i=low(n/2)的结点都是叶子，因此以这些结点为根的子树都已是堆。,（1）建堆次序,建大根堆,(c)只需依次将序号为low(n/2)low(n/2)-1，.，1的结点作为根的子树都调整为堆即可。,23,91,24,16,05,88,42,13,n/2,（1）建堆次序,(2)建堆方法-“筛选法”,一:如果Ri的左右子树已是堆，这两棵子树的根分别是各自子树中关键字最大的结点。,23,91,24,16,05,88,42,13,二:若根的关键字已是三者（根、左孩子、右孩子）中的最大者，则无须做任何调整；否则必须将具有最大关键字的孩子与根交换。,23,91,24,16,05,88,42,13,三:交换之后有可能导致新子树不再是堆，需要将新子树调整为堆。如此逐层递推下去，直到调整到树叶为止。,42,88,91,13,24,16,05,23,42,88,91,13,24,16,05,23,17,14,思考:如果最后一个节点不是14，而是12将如何？,例子：关键字序列为 42，13，91，23，24，16，05，88，n=8，故从第四个结点开始调整,42,13,91,23,24,16,05,88,42,13,91,23,24,16,05,88,42,13,91,88,24,16,05,23,42,13,91,88,24,16,05,23,不调整,42,13,91,88,24,16,05,23,42,13,91,88,24,16,05,23,42,88,91,23,24,16,05,13,42,88,91,23,24,16,05,13,91,88,42,23,24,16,05,13,91,88,42,23,24,16,05,13,建成的堆,42,13,91,88,24,16,05,23,42,13,91,88,24,16,05,23,m=2hm=t=13j=4 hj=88 hj+1=24,j,m,SIFT(ET h,int n;int m)int j;ET t;t=hm;j=2*m;while(j=n)/处理到叶子 if(jn),SIFT(ET h,int n;int m)int j;ET t;t=hm;j=2*m;while(j=n)/处理到叶子 if(jn),42,91,88,24,16,05,23,42,88,91,88,24,16,05,23,m=4 t=13hm=13j=8 hj=23 hn+1=0,13,j,m,SIFT(ET h,int n;int m)int j;ET t;t=hm;j=2*m;while(j=n)/处理到叶子 if(jn),42,91,88,24,16,05,13,42,13,91,88,24,16,05,23,m=8 t=13hm=23j=16,23,j,m,上述算法只是对一个指定的结点进行调整。有了这个算法，将初始的无序区R1到Rn建成一个大根堆，如何实现?,for(i=n/2 1;i=0;i-)SIFT(R,n-1,i),由于建堆的结果把关键字最大的记录选到了堆顶的位置，而排序的结果应是升序，如何解决?,3.堆排序算法,应该将R0和Rn-1交换，这就得到了第一趟排序的结果。,第二趟排序的操作首先是将无序区R0到Rn-2调整为堆。这时对于当前堆来说，它的左右子树仍然是堆，所以，可以调用SIFT函数将R0到Rn-2调整为大根堆，选出最大关键字放入堆顶，然后将堆顶与当前无序区的最后一个记录Rn-2交换，如此反复进行下去。,91,88,42,23,24,16,05,13,91,88,42,23,24,16,05,13,（a）初始堆R1到R8,举例：,13,88,42,23,24,16,05,91,13,88,42,23,24,16,05,91,（b）第一趟排序之后,（c）重建的堆R1到R7,88,24,42,23,13,16,05,91,88,24,42,23,13,16,05,91,05,24,42,23,13,16,88,91,05,24,42,23,13,16,88,91,（d）第二趟排序之后,（e）重建的堆R1到R6,42,24,16,23,13,05,88,91,42,24,16,23,13,05,88,91,（f）第三趟排序之后,05,24,16,23,13,42,88,91,05,24,16,23,13,42,88,91,（g）重建的堆R1到R5,24,23,16,05,13,42,88,91,24,23,16,05,13,42,88,91,（h）第四趟排序之后,13,23,16,05,24,42,88,91,13,23,16,05,24,42,88,91,（i）重建的堆R1到R4,23,13,16,05,24,42,88,91,23,13,16,05,24,42,88,91,（j）第五趟排序之后,05,13,16,23,24,42,88,91,05,13,16,23,24,42,88,91,（k）重建的堆R1到R3,16,13,05,23,24,42,88,91,16,13,05,23,24,42,88,91,（l）第六趟排序之后,05,13,16,23,24,42,88,91,05,13,16,23,24,42,88,91,（m）重建的堆R1到R2,13,05,16,23,24,42,88,91,13,05,16,23,24,42,88,91,（n）第七趟排序之后,05,13,16,23,24,42,88,91,05,13,16,23,24,42,88,91,HEAPSORT(ET p)int i;ET t;for(i=n/2-1;i=1;i-)sift(p,n-1,i);for(i=n-1;i=1;i-)t=p0;p0=pi;pi=t;sift(p,i-1,0);,4.堆排序的时间复杂度,堆排序的时间复杂性为O(nlog2n)空间复杂性为 O(1)堆排序是不稳定的排序方法。,堆排序课堂练习,23 33 21 1 24 14 2 26 90 431）先建大根堆（写出过程）2）排序！,七、归并排序,基本原理：通过对两个有序结点序列的合并来实现排序。所谓归并是指将若干个已排好序的部分合并成一个有序的部分。若将两个有序表合并成一个有序表，称为2-路归并。,1.两路归并的基本思想,(1)设有两个有序表A和B，对象个数分别为al和bl，变量i和j分别是两表的当前指针。,(2)设表C是归并后的新有序表，变量k是它的当前指针。,(3)i和j对A和B遍历时，依次将关键字小的对象放到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)将待排序列R1到Rn看成n个长度为1的有序子序列，把这些子序列两两归并，便得到high(n/2)个有序的子序列。(2)然后再把这high(n/2)个有序的子序列两两归并，如此反复，直到最后得到一个长度为n的有序序列。(3)上述每次归并操作，都是将两个子序列归并为一个子序列，这就是“二路归并”，类似地还可以有“三路归并”或“多路归并”。,算法评价,空间复杂度为O（n），用辅助空间L1、L2、（Swap）时间复杂度为O（nlogn）2-路归并排序算法是稳定的。,八、基数排序,多关键字排序技术：多关键字（K1,K2,Kt）;例如：关键字 K1 小的结点排在前面。如关键字 K1相同，则比较关键字 K2，关键字 K2 小的结点排在前面，依次类推,1.举例,假定给定的是 t=2 位十进制数，存放在数组 B 之中。现要求通过基数排序法将其排序。设置十个口袋，因十进制数分别有数字：0，1，2，9，分别用 B0、B1、B2、B9 进行标识。执行 j=1t(这里t=2)次循环，每次进行一次分配动作，一次收集动作。将右起第 j 位数字相同的数放入同一口袋。比如数字为 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,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。,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,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。,5,2,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=5、2、9、7、18、17、52,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。,5,2,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=5、2、9、7、18、17、52,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。,5,2,9,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=5、2、9、7、18、17、52,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。,5,2,9,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=5、2、9、7、18、17、52,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。,5,2,9,7,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=5、2、9、7、18、17、52,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。,5,2,9,7,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=5、2、9、7、18、17、52,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。,5,2,9,7,18,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=5、2、9、7、18、17、52,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。,5,2,9,7,18,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=5、2、9、7、18、17、52,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。,5,2,9,7,18,17,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=5、2、9、7、18、17、52,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。,5,2,9,7,18,17,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=5、2、9、7、18、17、52,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。,5,2,9,7,18,17,52,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=5、2、9、7、18、17、52,B0B1B2B3B4B5B6B7B8B9,口袋,分配完毕，按照 箭头所指的方向进行 收集动作。注意：收集后的序列已经按照右起第一位（个位数字）排好序了。,5,2,9,7,18,17,52,收集后的序列：2、52、5、7、17、18、9、,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=2、52、5、7、17、18、9（第一次收集的结果）,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。和第一次不同，这次根据右起第二位数字（十位数字）进分配。,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=2、52、5、7、17、18、9（第一次收集的结果）,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。和第一次不同，这次根据右起第二位数字（十位数字）进分配。,2,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=2、52、5、7、17、18、9（第一次收集的结果）,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。和第一次不同，这次根据右起第二位数字（十位数字）进分配。,2,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=2、52、5、7、17、18、9（第一次收集的结果）,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。和第一次不同，这次根据右起第二位数字（十位数字）进分配。,2,52,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=2、52、5、7、17、18、9（第一次收集的结果）,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。和第一次不同，这次根据右起第二位数字（十位数字）进分配。,2,52,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=2、52、5、7、17、18、9（第一次收集的结果）,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。和第一次不同，这次根据右起第二位数字（十位数字）进分配。,2,52,5,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=2、52、5、7、17、18、9（第一次收集的结果）,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。和第一次不同，这次根据右起第二位数字（十位数字）进分配。,2,52,5,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=2、52、5、7、17、18、9（第一次收集的结果）,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。和第一次不同，这次根据右起第二位数字（十位数字）进分配。,2,52,5,7,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=2、52、5、7、17、18、9（第一次收集的结果）,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。和第一次不同，这次根据右起第二位数字（十位数字）进分配。,2,52,5,7,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=2、52、5、7、17、18、9（第一次收集的结果）,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。和第一次不同，这次根据右起第二位数字（十位数字）进分配。,2,52,5,7,17,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=2、52、5、7、17、18、9（第一次收集的结果）,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。和第一次不同，这次根据右起第二位数字（十位数字）进分配。,2,52,5,7,17,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=2、52、5、7、17、18、9（第一次收集的结果）,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。和第一次不同，这次根据右起第二位数字（十位数字）进分配。,2,52,5,7,17,18,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=2、52、5、7、17、18、9（第一次收集的结果）,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。和第一次不同，这次根据右起第二位数字（十位数字）进分配。,2,52,5,7,17,18,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=2、52、5、7、17、18、9（第一次收集的结果）,B0B1B2B3B4B5B6B7B8B9,口袋,根据 所指向的 数，进行分配动作，将其分配到相应的口 袋。和第一次不同，这次根据右起第二位数字（十位数字）进分配。,2,52,5,7,17,18,9,基数排序举例,e.g:B=5、2、9、7、18、17、52 用基数排序法进行排序。B=2、52、5、7、17、18、9（第一次收集的结果）,B0B1B2B3B4B5B6B7B8B9,口袋,2,52,5,7,17,18,9,分配完毕，按照箭头所指的方向进行 第二次收集动作。注意：收集后的序列已经按照右起第一位（个位数字）、右起第二位（十位数字）排好序了。,收集后的序列：2、5、7、9、17、18、52已是排好序的序列。,性能分析,空间：采用顺序分配，显然不合适。由于每个口袋都有可能存放所有的待排序的整数。所以，额外空间的需求为 10n，太大了。采用链接分配是合理的。额外空间的需求为 n，通常再增加指向每个口袋的首尾指针就可以了。在一般情况下，设每个键字的取值范围为 rd,首尾指针共计 2rd 个，总的空间为 O(n+2rd)。,时间：上例中每个数计有 t=2 位，因此执行 t=2 次分配和收集就可以了。在一般情况下，每个结点有 d 位关键字，必须执行 t=d次分配和收集操作。分配的代价：O(n)收集的代价：O(rd)总的代价为：O(d(n+rd),课堂练习,23,44,55,45,21,124,115,7,129,99,3.4 二叉排序树及其查找,一、定义 所谓二叉排序树是指满足下列条件的二叉树：（1）左子树上的所有结点值均小于根结点值。（2）右子树上的所有结点值均不小于根结点值。（3）左、右子树也满足上述两个条件,二、二叉排序树的特性,二叉排序树有一个重要特性：中序遍历二叉排序树可以得到有序序列。因此，由无序序列构造二叉排序树实际上就将一个无序序列变成了有序序列。另外，由于在二叉排序树中插入的新结点都是叶子结点，因此，在对二叉排序树进行插入运算时，不需移动其他结点，而只需改动插入位置上的叶子结点指针即可。,三、二叉排序树的构造,依次读入给定序列中的每一个元素，然后进行如下处理：（1）若当前的二叉排序树为空，则读入的元素为根结点。（2）若读入的元素值小于根结点值，则将元素插入到左子树中。（3）若读入的元素值不小于根结点值，则将元素插入到右子树中。无论是插入到左子树还是右子树，都是同样按照上述方法处理。,四、二叉排序树的删除,为了删除一个元素，首先要找到被删除元素所在的结点p和它的父结点q，然后分以下3种情况进行处理：（1）p为叶子结点：直接删除，修改父结点指针。（2）p为单支树：将P的子树链到q上。（3）p的左右子树均不空：将p的左子树的右链最右边的结点s的值填入p中，将s的左链链到s的父结点的右指针。,五、二叉排序树查找算法,算法描述:输入一个值，在该树中查找，若找到输出该结点值；否则，显示查找失败。与根比，相等，查找成功，比根小，在左子树查比根大，在右子树查查左右子树时按同样的方法查,struct tree*search_btree(struct tree*root,char key)if(!root)cout