《数据结构与算法之内排序(powerpoint 87页)》由会员分享，可在线阅读，更多相关《数据结构与算法之内排序(powerpoint 87页)（88页珍藏版）》请在金锄头文库上搜索。
1、7 内排序主要内容内部排序内部排序/外部排序外部排序稳定稳定/不稳定排序不稳定排序排序算法性能分析排序算法性能分析内部排序算法内部排序算法2内排序设设n个记录的序列为个记录的序列为R1,R2,R3,.,Rn其相应的关键字序列为其相应的关键字序列为K1,K2,K3,.,Kn若规定若规定1,2,3,.,n的一个排列的一个排列p1,p2,p3,.,pn，使得相应的关键字满足如下非递减关系使得相应的关键字满足如下非递减关系:KpKpKp.Kp123n则原序列变为一个按关键字有序的序列则原序列变为一个按关键字有序的序列:Rp,Rp,Rp,.,Rp123n此操作过程称为此操作过程称为排序排序。排 序3内排
2、序内部排序内部排序:指的是待排序记录存放在计算机指的是待排序记录存放在计算机随机存储器随机存储器中进行的排序过程。中进行的排序过程。外部排序外部排序:指的是待排序记录的数量很大，以致内存一指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对次不能容纳全部记录，在排序过程中尚需对外存外存进行访进行访问的排序过程。问的排序过程。内部排序与外部排序4内排序假设假设Ki=Kj，且排序前序列中，且排序前序列中Ri领先于领先于Rj；若在排序后的序列中若在排序后的序列中Ri仍领先于仍领先于Rj，则称排序方法是，则称排序方法是稳定的稳定的。若在排序后的序列中若在排序后的序列中Rj仍领先
3、于仍领先于Ri，则称排序方法是，则称排序方法是不稳定的不稳定的。例，序列例，序列3158869若排序后得若排序后得3688915稳定的稳定的若排序后得若排序后得3688915不稳定的不稳定的稳定排序与不稳定排序5内排序排序的时间复杂性 排序过程主要是对记录的排序码进行比较和记录的移动过程。因此排序的时间复杂性可以算法执行中的数据比较次数及数据移动次数来衡量。 当一种排序方法使排序过程在最坏或平均情况下所进行的比较和移动次数越少，则认为该方法的时间复杂性就越好，分析一种排序方法，不仅要分析它的时间复杂性，而且要分析它的空间复杂性、稳定性和简单性等。6内排序按照排序过程中所依据的原则的不同可以分类
4、为按照排序过程中所依据的原则的不同可以分类为:插入排序插入排序交换排序交换排序选择排序选择排序归并排序归并排序基数排序基数排序二叉排序树排序二叉排序树排序内部排序7内排序思想思想:利用有序表的插入操作进行排序利用有序表的插入操作进行排序有序表的插入有序表的插入:将一个记录插入到已排好序的有序表中，将一个记录插入到已排好序的有序表中，从而得到一个新的有序表。从而得到一个新的有序表。例，序列例，序列132738657697插入插入4913273849657697插入排序直接插入排序8内排序例，序列例，序列49386597761327初始，初始，S=49；3849初始，令第初始，令第1个元素作为初始
5、有序表；个元素作为初始有序表；依次插入第依次插入第2,3,k个元素构造新的有序表；个元素构造新的有序表；直至最后一个元素；直至最后一个元素；38496538496597384965769713384965769713273849657697直接插入排序算法主要应用直接插入排序算法主要应用比较比较和和移动移动两种操作。两种操作。直接插入排序算法描述9内排序void insertsort(ElemType R,int n)/待排序元素用一个数组R表示，数组有n个元素 for ( int i=1; i=0)& (tempRj) Rj+1=Rj; j-; / 顺序比较和移动 Rj+1=temp; 10
6、内排序直接插入排序的效率分析直接插入排序的效率分析从空间来看，它只需要一个元素的辅助空间，用于元素的位置交换。从时间分析，首先外层循环要进行n-1次插入，每次插入最少比较一次（正序），移动两次；最多比较i次，移动i2次（逆序）（i=1，2，n-1）。Cmin=n-1 M min=2（n-1）Cmax=1+2+n-1=（n2-n）/2 M max=3+4+n+1=（n2+3n-4）/2Cave=（n2+n-2）/4 M ave=（n2+5n-6）/4因此，直接插入排序的时间复杂度为O（n2）。直接插入算法的元素移动是顺序的，该方法是稳定的。11内排序插入排序平均情况复杂度平均情况复杂度对每个对每
7、个 i 值，考虑平均情况下需要多少次比较。为简化分析，假值，考虑平均情况下需要多少次比较。为简化分析，假设所有的值是不相同的，对一个设所有的值是不相同的，对一个 i 和临时变量和临时变量 x， x 有有 i+1 个位置可能会去个位置可能会去 0 1 2 .i-1 x=Ai比较次数和插入位置的关系：i=6A0 A1 A2 A3 A4 A5 x=A6插入位置插入位置6543210比较次数比较次数123456612内排序插入排序平均情况复杂度平均情况复杂度 在对序列没有其它任何信息的条件下在对序列没有其它任何信息的条件下, x 到任何一个位置的概率到任何一个位置的概率都是都是1/(i+1). 这样这
8、样, 对一个特定的值对一个特定的值i , 需要的平均比较次数需要的平均比较次数为为:把所有把所有n-1次插入累加起来次插入累加起来, 有有: 13内排序由于直接插入排序算法利用了有序表的插入操作，由于直接插入排序算法利用了有序表的插入操作，故故顺序查找顺序查找操作可以替换为操作可以替换为折半折半(二分法二分法)查找查找操作。操作。例，序列例，序列49386597761327设已形成有序表设已形成有序表384965769713插入元素插入元素13折半插入排序leftrightmidrightmid0 1 2 3 4 5right97766549381314内排序算法算法:void BinaryI
9、nsertSort(ElemType R,int n) for(int i=1; in; i+) /共进行n-1次插入 int left=0,right=i-1;ElemType temp=Ri; while(left=right) int middle=(left+right)/2; /取中点 if (temp=left;j-) Rj+1=Rj; /元素后移空出插入位 Rleft=temp; 15内排序折半插入效率分析二分插入算法与直接插入算法相比，需要辅助空间与直接插入排序基本一致；时间上，前者的比较次数比直接插入查找的最坏情况好，最好的情况坏，两种方法的元素的移动次数相同，因此二分插入排
10、序的时间复杂度仍为O(n2)。二分插入算法与直接插入算法的元素移动一样是顺序的，因此该方法也是稳定的。16内排序分析直接插入排序分析直接插入排序1.若待排序记录序列按关键字若待排序记录序列按关键字基本有序基本有序，则排序效，则排序效率可大大提高；率可大大提高；2.待排序记录总数越少，排序效率越高；待排序记录总数越少，排序效率越高；希尔(shell)排序17内排序思想思想:先将待排序记录序列分割成为若干子序列分别进行直接插入排序；先将待排序记录序列分割成为若干子序列分别进行直接插入排序；待整个序列中的记录基本有序后，再全体进行一次直接插入排序。待整个序列中的记录基本有序后，再全体进行一次直接插入
11、排序。例，序列例，序列493865977613274855419第一趟排序第一趟排序49131938276548975576413194927384865559747618内排序第二趟排序第二趟排序131949273848655597476135538762746549481997133855764274965194897第三趟排序第三趟排序41319273848495565769719内排序653425871238564614779223563414771223654625879238结果序列结果序列d=65634147712236546258792385612146534237746258
12、79238结果序列结果序列d=3561214653423774625879238121423253438465665778792结果序列结果序列d=1(a)(b)(c)希尔排序的排序过程希尔排序的排序过程0 0 1 2 3 4 5 1 2 3 4 5 6 6 7 8 9 10 11 7 8 9 10 110 0 1 2 1 2 3 3 4 5 4 5 6 6 7 8 7 8 9 9 10 11 10 1120内排序希尔排序的算法希尔排序的算法templatevoidShellSort (T Vector, int arrSize ) T temp; int gap = arrSize / 2;
13、/gap是子序列间隔 while ( gap != 0 ) /循环,直到gap为零for ( int i = gap; i = gap; j -= gap ) if ( temp Vectorj-gap ) Vectorj = Vectorj-gap;elsebreak;Vectorj = temp;gap = ( int ) ( gap / 2); 21内排序希尔排序效率分析希希尔尔排排序序的的时时间间复复杂杂性性在在O（nlog2n）和和O（n2）之之间间，大致为大致为O（n1.3）。）。（Flash动画演示）动画演示）希尔排序是不稳定的排序算法。希尔排序是不稳定的排序算法。22内排序思想
14、思想:通过不断比较相邻元素大小，进行交换来实现排序。通过不断比较相邻元素大小，进行交换来实现排序。首先将第一个元素与第二个元素比较大小，若为逆序，则交换；首先将第一个元素与第二个元素比较大小，若为逆序，则交换；然后比较第二个元素与第三个元素的大小，若为逆序，则交换；然后比较第二个元素与第三个元素的大小，若为逆序，则交换；.直至比较第直至比较第n- -1个元素与第个元素与第n个元素的大小，若为逆序，则交换；个元素的大小，若为逆序，则交换；第一趟排序第一趟排序:结果结果:关键字最大关键字最大的记录被交换至的记录被交换至最后最后一个元素位置上。一个元素位置上。交换排序冒泡排序23内排序交换排序冒泡排
15、序优点优点： 每每趟趟结结束束时时，不不仅仅能能挤挤出出一一个个最最大大值值到到最最后后面面位位置置(或或者者最最小小值值到到最最前前面面位位置置)，还还能能同同时时部部分分理理顺顺其其他他元元素素；一一旦旦下下趟趟没没有有交交换换发发生生，还还可以可以提前结束排序提前结束排序。24内排序例，序列例，序列4938761327493876132738491327384913762776初始初始第一趟排序后第一趟排序后最大值最大值13492749次大值次大值第二趟排序后第二趟排序后38132713271338 2738第三趟排序后第三趟排序后第四趟排序后第四趟排序后25内排序冒泡排序的算法实现冒泡
16、排序的算法实现。void Bubblesort(ElemType R,int n) int flag=1; /当flag为0则停止排序 for (int i=1; i=i; j-) if (RjRj-1) /发生逆序 ElemType t=Rj;Rj=Rj-1;Rj-1=t; flag=1; /交换，并标记发生了交换 if(flag=0)return; 26内排序冒泡排序的效率分析冒泡排序的效率分析最好情况：若待排序的元素为正序，则只需进行一趟排序，比较次数为（n-1）次，移动元素次数为0；最坏情形：初始排列逆序，算法要执行n-1趟排序，第i趟(1 i n) 做了n- i 次关键码比较，执行了3(n-i )次数据元素交换。此时的比较总次数和记录移动次数为：因此冒泡排序算法的时间复杂度为O（n2）。由于其中的元素移动较多，所以属于内排序中速度较慢的一种。因为冒泡排序算法只进行元素间的顺序移动，所以是一个稳定的稳定的算法。27内排序冒泡排序的一种改进算法。冒泡排序的一种改进算法。思想思想:以以首记录首记录作为作为轴记录轴记录，从前、后双向扫描序列，通过交换，实，从前、后双向扫描序列，通过交
