资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,.10(2),.,:,1,选择排序(简单选择排序、堆排序),2,3,10.4 选择排序,基本思想：每一趟从待排序的记录中选出最小(或最大)的记录(简称最小元)，放在已排好序的子区间最后,10.4.1 直接选择排序(简单选择),基本思想：,第1趟，无序区为R1，选最小者放在R1，无序区变为2.,第i趟，有序区为R11，无序区为R,显然R11R,选无序区中最小者Rk，交换Ri和Rk后使R1 R1 有序区长度加1，无序区长度减1,第1趟之后，R11 Rn，结束,4,10.4,： ( ) .,10.4.1,：, R1， R1, R2., R11, . Ri. , R1, R1.,(1) , , .,5,10.4,我们的算法是每次选最小元，教材每次选最大元,6,10.4,7, 10.4.1,算法,( R),i, j, k;,(1; in; ) 外循环，第i趟排序，1i 1,k = i; 用于存放某次循环的最大或最小元下标,(1; j; ),在当前无序区R中选最小的记录Rk,(Rj 0; ) ,= (0, );,(),(, );,:, : ( , ),/* : = .,: .,: . 6.*/, ;,= ;,( = +1; = ; ),( 1; ) 进行1趟堆排序，当前无序区为R1,R1 Ri; 无序区首尾记录交换，R0做暂存单元,( R,11 ); 将R11重新调整为堆,如何调整堆和构造初始堆？,21, 10.4.2 堆排序,调整（重建）堆,设调整区间为R，因为只有根R违反堆序，它的两子树（若存在，则根为R2，R21）均是堆。,无须调整 若R不小于两孩子的，则R不违反堆序,必须调整 将R和它的两孩子中较大者交换：,设R R2, R21 ,令R R,交换后R可能违反堆序，重复上述过程，直至被调整的结点已满足堆序，或该结点已是叶子。,20,10,56,25,30,15,56,10,25,20,30,15,56,10,20,25,30,15,22, 10.4.2,R R. , , R , R .,: R , .,: ：,R R R2, R21 ,R , a .,20,10,56,25,30,15,56,10,25,20,30,15,56,10,20,25,30,15,23, 10.4.2,调整堆算法,( R, , ) ,; 只有R可能违反堆序,;,( 2*; ，则R是叶子，结束；,否则，先令指向R的左孩子,( R ) ; 满足堆序,R; 交换，小的筛下,; 令指向新的调整结点,R; 将被调整结点放到最终的位置,24, 10.4.2 堆排序,构造初始堆算法,将R1建成堆，须将其每个结点为根的子树均调整为堆。对叶子(i )无须调整，只要依次将以序号为 , , , 2, 1的结点为根的子树均调整为堆即可。按此次序调整每个结点时，其左右子树均已是堆,( R ) ,i;,( 2; i0; ),( R, i, n); 将R 调整为堆,时间：最坏及平均皆为O() (2(n),特点：就地，不稳定,25, 10.4.2, 10.4.2, 10.4.2 ( ), : ( ),;,;,( ); : a .,( = - 1; 0 ) ,= ; ., _ = 0;,(, 0, - 1);,28, 10.4.2 ( ),a, :,( , , ),; ,= 2 * + 1; .,( = ) ,( = ),.,;,29, 10.4.2 ( ), ., = ;,= ;,= 2 * +1;, = ;,30, : ( ),/* : a .,: 6, . */,; a .,( = 2 - 1; = 0; ) ,= ;,(, , - 1);, 10.4.2,32,大根堆排序示例,91,16,88,23,42,24,05,13,【91 88 42 23 24 16 05 13】,13,16,88,23,42,24,05,91,【13 88 42 23 24 16 05】91,88,16,24,23,42,13,05,91,【88 24 42 23 13 16 05】91,05,16,24,23,42,13,88,91,【05 24 42 23 13 16】88 91,初始堆R1.8,第一趟排序:交换后,1趟:重建堆R1.7后,第二趟排序:交换后,33,归并排序(顺序实现、链表上的实现),34, 10.5,： . , a .,35, 10.5,初始关键字,49 38 65 97 76 13 27,第一趟归并后, 38 49 65 97 13 76 27 ,第二趟归并后, 38 49 65 97 13 27 76 ,第三趟归并后, 13 27 38 49 65 76 97 ,36, 10.5,：,( R, , m, ) ,将2个有序表R和R1归并为1个有序表R, 1, 0; 指向输入子表头，p指向输出子表,*R1=( *)(1)*()输出,( 1 )( “存储分配失败” ),( i j ) 2子表非空时，取其头上较小者输出到R1p上,R1=( Rij ) ? R : R ;,( i ) 第1子表非空，将剩余记录到R1中,R1 ;,( j ) , * = ();,( );,();,= (, );, * :,( *), *,*,* ;,( = ) ) ;,= ;,( ) s,= ;,( ) ,= ;,= ;,= ;, = ;,;, 10.5,43, * :,( *, *), *;, ;,= ;,( ) ,( ) , = ;,= ;,= ; ., = ;,= ;,= ;, , .,( ), = ;, = ;,;,（归并排序）, 10.5,47,树的高度体现了最坏情况下的比较次数,平均查找次数=树的外部路径长度/叶结点数,叶结点数至少为n！,根据 7.5 7.6 ,外部路径长度至少n!,最坏情况，,平均情况：!,! ,以关键字比较为基础的排序，关键字的比较次数的数量级起码为O(),分配排序(基数排序),49, 10.6 分配排序,基于比较的排序时间下界:,由公式知：!1.44(),要突破此界，就不能通过的比较。,分配排序正是如此，它通过“分配”和“收集”过程实现排序，时间为O(n)。,10.6.1 箱排序,基本思想,分配：扫描R01,将等于k的记录全装入箱子里,收集：按序号将各非空箱子首尾连接起来,多趟：每个关键字1趟，例如:扑克牌,时间：,分配：O(n)；,收集：设箱子数为m(与相关)，时间为O(m)或O(),总计：O()(n) (n),50,10.6.2 基数排序,基本思想,箱排序只适用于取值范围小的情况，否则浪费时间和空间。,例如，若mO(n2), 则时间和空间均为O(n2)。,基数排序是通过分析的构成，用多趟箱排序实现的。,例子,设n10，0.99, 1i 10,输入:（36,5,10,16,98,95,47,32,36,48）,将2位整数看作2个，先对个位，后对十位做箱排序。因此，无须100个箱子，只要10个箱子。,51,10.6.2 基数排序,第,1,趟箱排序,分配：,0 10,1,2 32,3,4,5 5,95,6 36,16,36,7 47,8 98,48,9,收集：,10,32,5,95,36,16,36,47,98,48,（,36,5,10,16,98,95,47,32,36,48,）,第,2,趟箱排序,分配：,0 05,1 10,16,2,3 32,36,36,4 47,48,5,6,7,8,9 95,98,收集：,05,10,16,32,36,36,47,48,95,98,各趟排序前要求清空箱子，分配和收集须按进行，箱子用链队列表示。,除第1趟外，其余各趟一定要是稳定的排序，否则结果可能有错。,m不再在数量级上大于O(n)，故上述排序时间是O(n),52,10.6.2 基数排序,一般情况,设任一记录Ri的均由d个分量 0 , 1 , , 1 构成,多关键字文件：d个分量皆为独立的,单关键字文件：每个分量是中的1位，只讨论这种情况。,设每位取值范围相同：,C01 (0jd),这里，称为基数，d为的位数。,若为十进制整数，按位分解后10，C00，C99,排序算法,从低位到高位依次对（j12,0）进行d趟箱排序，所需的箱子数为基。,4 设d4,10 基为10,; 各箱子用链队列表示，其中的结点数据类型改为与本章的记录类型一致,53,10.6.2 基数排序,( R ),对R01做基数排序，设为非负整数，,且位数不超过,B; 10个箱子,i；,( 0; i=0; ) ,对位i箱排序，从低位到高位进行d趟箱排序,( ); 分配,( ); 收集,54,10.6.2 基数排序,( R, B , j ),i，k，t； 按关键字分量分配，进入此过程时各箱子为空,- j; 将 j 换算为从个位起算，个位是第1位,( 0; in; ) 扫描R，装箱,i;,( 1; tj; ) 10; 去掉的后1位,10; 取的第j位数字k,( ki ); 将Ri装入箱子Bk,( R, B ),0, j; 依次连接各非空箱子，完成后使各箱子变空,( 0; j1)，则的位数是：,d1010nO(),因此，基数排序的时间是O()。但是可将其改为n进制表示：,n， dk，T(n)O( k() )(n),辅助空间：O(),对的要求：,稳定排序：要求第1趟稳定，其余各趟必须稳定。,56,10.6.2 基数排序,链式基数排序：文件R不是以向量形式，而是以单链表形式给出。,时间：线性阶,箱子初始化：O(),分配时间：O(n)，不计求第j位数字的时间,收集收集：O()，链式为O(),d趟总时间：O( d(2) )，链式为O( d() ),T(n)(n) (1) (1) O(n),设是十进制整数，d是常数吗？,若n个的取值范围是0 ，(常数k1)，则的位数是：,d1010nO(),因此，基数排序的时间是O()。但是可将其改为n进制表示：,n， dk，T(n)O( k() )(n),辅助空间：O(),对的要求：,稳定排序：要求第1趟稳定，其余各趟必须稳定。,57, 10.6,58,10.6.2, . a .,n10, 0.99, 1i 10,:(36,5,10,16,98,95,47,32,36,48),(1s ) :,(10,32,5,95,36,16,36,47,98,48),(10s ) :,(05,10,16,32,36,36,47,48,95,98),a 0 9, .,59,10.6.2,1,st,pass,Scatter,：,0 10,1,2 32,3,4,5 5,95,6 36,16,36,7 47,8 98,48,9,Gather,：,10,32,5,95,36,16,36,47,98,48,(36,5,10,16,98,95,47,32,36,48),2,nd,pass,Scatter,：,0 05,1 10,16,2,3 32,36,36,4 47,48,5,6,7,8,9 95,98,Gather,：,05,10,16,32,36,36,47,48,95,98, . .,.,60,10.6.2,61,10.6.2 ( ),: ,:,();,:,( );,;,:,( ) ;,();,();,;,62,10.6.2 ( ),28;,(),;,;,( 1=0),(0),();,();,();,63,10.6.2 ( ),&,( c),( ) 0;,(a c=z) a+1;,(A c= Z) A+1;,27;,( ),;,( 0),(i(),i();,();,i();,64,10.6.2,： .,：,：O(),：O(n),：O() , O(),：O( d(2) ) , O( d() ),T(n)(n) (1) (1) O(n), d a ?,0 , (k a 1), # ：,d1010nO(),O(). 10 n：,n， dk，T(n)O( k() )(n),：O(),., .,65,10.7,各种排序方法的比较和选择,选择因素：,实例规模，记录大小，,key,的结构及初始状态，对稳定性的要求，存储结构，时间和辅助空间的要求，语言工具,(,指针,),。,比较,n,直接插入,直接选择,冒泡排序,堆排序,快速排序,随,4000,8000,10000,15000,机,20000,增,20000,减,20000,5.67,23.15,35.43,80.23,143.67,0.05,286.92,17.30,29.43,46.02,103.00,185.05,185.78,199.00,15.78,64.03,99.10,223.28,399.47,0.03,584.67,0.13,0.28,0.35,0.58,0.77,0.75,0.80,0.07,0.17,0.22,0.33,0.47,0.23,0.28,说明,直接选择无论,k,和,i,是否相等，均交换；快排用中间元做划分元。,66,
展开阅读全文