算法课件--第9章(内排序)

NorthChinaElectricPowerUniversity第九章内排序★基本概念★插入排序★冒泡排序★选择排序★计数排序★希尔排序★堆排序★快速排序★合并排序★基数排序NorthChinaElectricPowerUniversity设含有n个记录的文件{R1,R2,…，Rn},其相应的关键字为{K1,K2,…，Kn}，需确定一种排列P(1),P(2),…,P(n),使其相应的关键字满足如下的递增(或递减)关系：KP(1)≤KP(2)≤KP(3)≤…≤KP(n)即，使上述文件成为一个按其关键字线性有序的文件{RP(1),RP(2),…，RP(n)},这样一种运算称为排序。9.1基本概念如果在排序期间具有相同关键字的记录的相对位置不变，则称此方法是稳定的。排序：排序的稳定性：NorthChinaElectricPowerUniversity即，1)K(i)≤K(i+1)(1≤i≤n-1)2)若在输入文件中ij,且Ki=Kj,则在经过排序后的文件中仍Ri先于Rj排序内排序：整个排序过程都在内存进行的排序。外排序：当文件很大以至于内存不足以存放全部记录，在排序过程中需要对外存进行存取访问。例如：将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,80,97NorthChinaElectricPowerUniversity内部排序的方法在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。使有序区中记录的数目增加一个或几个的操作称为一趟排序。存放待排序数据的数据结构：typedefstruct{intkey;datatypeotheritem;//其他域}records;typedefstructrecordsList[n+1];NorthChinaElectricPowerUniversity逐步扩大记录有序序列长度的方法大致有下列几类：1.插入类:将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度；2.交换类:通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度；3.选择类:从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度；4.归并类:通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度；5.其它方法。NorthChinaElectricPowerUniversity内排序插入类排序直接插入排序折半插入排序希尔排序交换类排序冒泡排序快速排序选择类排序选择排序堆排序归并类排序归并排序其他排序计数排序基数排序NorthChinaElectricPowerUniversity9.2计数排序对每个记录计算文件中有多少个其它记录的关键字大于该记录的关键字值，从而找到该记录的正确排序位置。keyinfocount设一个记录有三个域：关键字域该记录的其他信息域计数域排序算法的思想：NorthChinaElectricPowerUniversityfor(i=1;in;i++)for(j=i+1;j=n;j++)if(R[i].key)R[j].key)R[i].count=R[i].count+1;elseR[j].count=R[j].count+1;}voidcountsort(ListR,intn){for(i=1;i=n;i++)R[i].count=1;//对所有元素的count域置1；算法如下：NorthChinaElectricPowerUniversity设文件有n个记录，则外循环：i=1时，内循环要做n-1次比较；i=2时，内循环要做n-2次比较；…i=n-1时，内循环要做1次比较；总的比较次数为(n-1)+(n-2)+…+1=n(n-1)/2算法性能分析：所以，算法所需时间为O(n2)，由于不需要记录移动和额外空间，同时算法简单，当n较小时，可采用本算法。NorthChinaElectricPowerUniversity例关键字序列{46，55，13，42，44，17，05，70}关键字4655134244170570初始化11111111i=131222221i=232333331i=332733341i=432753451i=532754561i=632754671i=732754681NorthChinaElectricPowerUniversity9.3直接插入排序假设在排序过程中，记录序列R[1..n]的状态为：则一趟插入排序的基本思想为：将记录R[i]插入到有序子序列R[1..i-1]中，使记录的有序序列从R[1..i-1]变为R[1..i]。显然，完成这个“插入”需分三步进行：1．查找R[i]的插入位置j+1；2．将R[j+1..i-1]中的记录后移一个位置；3．将R[i]复制到R[j+1]的位置上。NorthChinaElectricPowerUniversity直接插入排序：利用顺序查找实现“在R[1..i-1]中查找R[i]的插入位置”的插入排序。注意直接插入排序算法的三个要点：1.从R[i-1]起向前进行顺序查找，监视哨设置在R[0]；R[0]=R[i]；{设置“哨兵”}j=i-1;while(R[0].keyR[j].key)j=j-1;{//从后往前找}Return(j+1);{返回R[i]的插入位置为j+1}2.对于在查找过程中找到的那些关键字不小于R[i].key的记录，并在查找的同时实现记录向后移动；while(R[0].keyR[j].key){R[j+1]=R[j];j=j-1;}3.i=2，3，…,n,实现整个序列的排序。NorthChinaElectricPowerUniversity排序算法如下：voidinsort(Listr,intn){//r为给定的表，其记录为r[i]，i=0，1，…，n，x为暂存单元。for(i=2;i=n;i++){r[0]=r[i];//r[0]作为标志位j=i-1;while(r[0].keyr[j].key){r[j+1]=r[j];j--;}//j从i-1至0，r[j].key与r[i].key进行比较r[j+1]=r[0];}}//insortNorthChinaElectricPowerUniversity排序的时间分析：实现排序的基本操作有两个：（1）“比较”序列中两个关键字的大小；（2）“移动”记录。对于直接插入排序：最好的情况（关键字在记录序列中顺序有序）：最坏的情况（关键字在记录序列中逆序有序）：“比较”的次数：“移动”的次数：总的说来，直接插入排序所需进行关键字间的比较次数和记录移动的次数均为n2/4，所以直接插入排序的时间复杂度为O(n2)。“比较”的次数：“移动”的次数：2(n-1)NorthChinaElectricPowerUniversity9.4折半插入排序排序算法的思想：由于直接插入排序的内循环(从1到i-1)的查找(或说是比较)是在(部分)有序表的环境下进行的，所以内循环用“折半查找法”，比用顺序查找法快。NorthChinaElectricPowerUniversity算法描述如下：voidbinsort(Listr,intn){for(i=2;i=n;i++){r[0]=r[i];low=1;high=i-1;while(low=high){m=(low+high)/2;ifr[0].keyr[m].keyhigh=m-1;elselow=m+1;}for(j=i-1;j=low;j--)r[j+1]=r[j];//把从第low起到第i-1各记录后移r[low]=r[0];//将第i个记录插入}}//binsortNorthChinaElectricPowerUniversity9.5冒泡排序排序算法的思想：比较k1和k2,如果这些关键字的值不符合排序顺序,就交换k1和k2；然后对记录k2和k3,k3和k4等等进行相同的工作。直到kn-1和kn为止,到此得到一个最大(或最小)关键字值存在kn的位置上(通常将此过程叫做一趟)。重复这个过程,就得到在位置kn-1,kn-2等处的适当记录,使得所有记录最终被排好序。例如:将5个记录的关键字7,4,8,3,9进行冒泡排序。排序后k1≤k2≤…≤kn(n=5)。7443347344837773888899999①②③④因为到第四趟就没有交换的偶对了,所以整个排序结束。NorthChinaElectricPowerUniversity算法描述如下:voidbubblesort(Listr,intn){for(m=1;m=n;m++)scanf(“%d”,r[m]);k=n;do{all=〝T〞;//all=T,标志没有交换的;all=F,标志有交换的for(m=1;m=k-1;m++){i=m+1;if(r[m]r[i]){max=r[m];r[m]=r[i];r[i]=max;all=〝F〞;}}k--;}while((all==〝F〞)&&(k!=1)}冒泡排序的结束条件为：最后一趟没有进行“交换”。冒泡排序是一种稳定的排序算法。NorthChinaElectricPowerUniversity时间分析:最好的情况（关键字在记录序列中顺序有序）：只需进行一趟起泡“比较”的次数：“移动”的次数：n-10最坏的情况（关键字在记录序列中逆序有序）：需进行n-1趟起泡“比较”的次数：“移动”的次数：NorthChinaElectricPowerUniversity9.6希尔排序基本思想：对待排序记录序列先作“宏观”调整，再作“微观”调整。所谓“宏观”调整，指的是，“跳跃式”的插入排序。即：将记录序列分成若干子序列，每个子序列分别进行插入排序,待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。假设将n个记录分成d个子序列，则这d个子序列分别为：{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}{R[2]，R[2+d]，R[2+2d]，…，R[2+kd]}…{R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d]}其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。NorthChinaElectricPowerUniversity例如：第二趟希尔排序，设增量d=3第三趟希尔排序，设增量d=1NorthChinaElectricPowerUniversity希尔排序的算法描述如下:voidShellInsert(Listr,intd)//本算法对直接插入算法作了以下修改：//1.前后记录位置的增量是d，而不是1；//2.r[0]只是暂存单元，不是哨兵。当j=0时，插入位置已找到。{for(i=d+1;i=n;i++)if(r[i]r[i-d])//需将r[i]插入有序增量子表{r[0]=r[i];//暂存在R[0]j=i-d;while((j0)and(r[0]r[j])){r[j+d]=r[j];//记录后移，查找插入位置j=j-d;}r[j+d]=r[0];//插入}}for(i=2;i=n;i++){r[0]=r[i];j=i-1;while(r[0].keyr[j].key){r[j+1]=r[j];j=j-1;}r[j+1]=r[0];}NorthChinaElectricPowerUniversityVoidShell_sort(Listr,intdlta,intt);{//按增量序列dlta[0..t-1]对顺序表r作希尔排序for(k=0;k=t;k++)ShellInsert(r,dlta[k]);}NorthChinaElectricPowerUniversity先取定一个两项之间的距离d1(≤n,其中n