数据结构第章排序插入排序和交换排序.pptx

武汉科技大学Wuhan University of Science and Technology张 凯计算机学院 软件工程系2011年3月12日第第1010章章 内部排序内部排序选择排序(直接排序、堆排序)概述插入排序(直接排序、折半排序、希尔排序)交换排序(冒泡排序、快速排序)归并排序基数排序v概述概述10.1概述概述排序：将数据元素的一个任意序列，重新排列成一个按关键字有序的序列。例：将关键字序列：52,49,80,36,14,58,61,23调整为：14,23,36,49,52,58,61,80若按主关键字排序则结果惟一若按次关键字排序则结果可以不惟一(因有相同关键字)v概述概述10.1概述概述设Ki、Kj(1in,1jn,ij)分别为记录Ri、Rj 的关键字，且Ki=Kj，在排序前的序列中Ri领先于Rj(即i j)。若在排序后的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的；反之，则称所用的排序方法是不稳定的。例：设排序前的关键字序列为：52,49,80,36,14,58,36,23若排序后的关键字序列为：14,23,36,36,49,52,58,80，则排序方法是稳定的。若排序后的关键字序列为：14,23,36,36,49,52,58,80，则排序方法是不稳定的。v概述概述10.1概述概述内部排序和外部排序若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。v插入排序插入排序10.2插入排序插入排序直接插入排序初始状态4938659776132749 R0R1R2R3R4R5R6R7R8i=2i=33849659776132749i=43849659776132749i=5384965769713274976i=6384965769713274913i=7384965769713274927i=83849657697132749494938659776132749 3849387趟排序1趟排序2趟排序排序过程排序过程：先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。v直接插入排序直接插入排序10.2插入排序插入排序voidInsertSort(SqList&L)/对顺序表L作直接插入排序。for(i=2;i=L.length;+i)if(L.ri.keyL.ri-1.key)/InsertSort在r1.i-1中查找ri的插入位置;对于在查找过程中找到的那些关键字不小于ri.key的记录，在查找的同时实现记录向后移动；插入ri;L.r0=L.ri;/复制为监视哨L.ri=L.ri-1;for(j=i-2;L.r0.keyL.rj.key;-j)L.rj+1=L.rj;/记录后移L.rj+1=L.r0;/插入到正确位置v直接插入排序性能分析直接插入排序性能分析10.2插入排序插入排序比较次数：移动次数：0最好的情况：待排序记录按关键字从小到大排列（正序）比较次数：移动次数：最坏的情况：待排序记录按关键字从大到小排列（逆序）v直接插入排序性能分析直接插入排序性能分析10.2插入排序插入排序由于待排记录序列是随机的，取上述二值的平均值。所以直接插入排序的时间复杂度为O(n2)。直接插入排序是“稳定的”：关键码相同的两个记录，在整个排序过程中，不会通过比较而相互交换。v折半折半插入排序插入排序10.2插入排序插入排序(1)基本思想考虑到L.r1,.,i-1是按关键字有序的有序序列，则可以利用折半查找实现“L.r1,i-1中查找L.ri的插入位置”如此实现的插入排序为折半插入排序。例：有例：有6个记录，前个记录，前5个已排序的基础上，对第个已排序的基础上，对第6个记录排序。个记录排序。15273653694215273653694215273653694215273642536910.2插入排序插入排序(high36)(4253)highmidlowlowhighmidhighlow折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。v折半插入排序折半插入排序算法算法10.2插入排序插入排序voidBinsertSort(SqList&L)/折半插入排序inti,low,high,mid;for(i=2;i=L.length;+i)L.r0=L.ri;/将L.ri暂存到L.r0low=1;high=i-1;While(low=high)/比较，折半查找插入位置mid=(low+high)/2;/折半if(L.r0.key=low;j)L.rj+1=L.rj;/记录后移L.rlow=L.r0;/插入/BInsertSortv折半插入排序折半插入排序算法分析算法分析10.2插入排序插入排序折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快。折半插入排序减少了关键字的比较次数，但记录的移动次数不变，其时间复杂度与直接插入排序相同。在插入第i 个对象时，需要经过log2i+1次关键码比较，才能确定它应插入的位置。折半插入排序是一个稳定的排序方法。v2-路插入排序路插入排序10.2插入排序插入排序(1)基本思想2-路插入排序是在折半插入排序的基础上改进的，目的是减少排序过程中移动记录的次数，但为此需要n个记录的辅助空间。v2-路插入排序路插入排序10.2插入排序插入排序(2)具体做法另设一个和L.r同类型的数组d，首先将L.r1赋值给d1，并将d1看成是在排好序的序列中处于中间位置的记录，然后从L.r中第2个记录起依次插入到d1之前或之后的有序序列中。先将待插入记录的关键字和d1的关键字进行比较。若L.rid1.key，则将L.ri插入到d1之前的有序表中。反之，插入到d1之后的有序表中。【初始关键字】4938659776132749排序过程中d的状态如下：i=1:(49)i=2:(49)(38)i=3:(4965)(38)i=4:(496597)(38)i=5:(49657697)(38)i=6:(49657697)(1338)i=7:(49657697)(132738)i=8:(4949657697)(132738)finalfirst2路插入排序过程示例：firstfinalfinalfirstfinalfirstfinalfirstfinalfirstfinalfirstfinalfirstvoidPath2Insertion(SqList&L,SqList&d)d0=L1;/L中D的第一个记录为d中排好序的记录。intfirst=0,final=0;/first、final分别指示d中排好序的记录的第1个和最后1个记录的位置for(inti=2;i=length;+i)/依次将L的第2个最后一个记录插入d中。if(Lidfinal)/待插入记录大于d中最小值，插入到dfinal之后final=final+1;dfinal=Li;else/待插入记录大于d中最小值，小于d中最大值，插入到d的中间(需要移动d数组)intj=final+;/移动d尾部元素以便按序插入记录。while(Lidj)d(j+1)%length=dj;j=(j-1+length)%length;dj+1=Li;for(inti=1;i=length;i+)/循环把d赋给L。Li=d(i+first-1)%length;/线性关系。v2-路插入排序路插入排序10.2插入排序插入排序2-路插入排序只能减少移动记录的次数，而不能绝对避免移动记录。2-路插入排序中，移动记录的次数约为n2/8。当L.r1是待排序记录中关键字最小或最大的记录时，2-路插入排序就完全失去了它的优越性。v表表插入排序插入排序10.2插入排序插入排序(1)基本思想通过改变排序过程中采用的存储结构，减少在排序过程中进行“移动”记录的操作。利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整到它们所应该在的位置上。v表表插入排序插入排序10.2插入排序插入排序#defineMAXSIZE100/静态链表容量TypedefstructRcdTyperc;/记录项intnext;/指针项SLNode;/表结点类型TypedefstructSLNoderMAXSIZE+1;/0号单元为表头结点intlength;/链表当前长度SLinkListType;/静态链表类型(2)待排记录序列的存储结构v表表插入排序插入排序10.2插入排序插入排序(3)具体做法首先将静态链表中数组下标为“1”的分量(结点)和表头结点构成一个循环链表，然后依次将下标为“2”至“n”的分量(结点)按记录关键字非递减有序插入到循环链表中。10.2插入排序插入排序voidTableSort(int*a,intn)nexthead=0=-1;for(i=1;in;i+)if(ai=ahead)nexti=head;head=i;elsep=head;while(nextp!=-1&anextpai)p=nextp;nexti=nextp;nextp=i;初始状态012345678MAXINT493865977613274910-i=3012345678MAXINT4938659776132749201-key域next域i=2012345678MAXINT493865977613274910-38123650i=4012345678MAXINT49386597761327492310-9740i=5012345678MAXINT493865977613274923140-i=6012345678MAXINT4938659776132749231504-i=7012345678MAXINT49386597761327496315042-i=8012345678MAXINT493865977613274963150472-7645136227724938v表表插入排序插入排序10.2插入排序插入排序(4)表插入排序性能分析从表插入排序的过程可见，表插入排序的基本操作仍是将一个记录插入到已排好序的有序表当中。和直接插排序相比，不同之处仅是以修改2n次指针值代替移动记录，排序过程中所需进行的关键字间的比较次数相同。因此表插入排序的时间复杂度仍是O(n2)。v表表插入排序插入排序10.2插入排序插入排序(4)表插入排序性能分析表插入排序的结果只是求得一个有序链表，则只能对它进行顺序查找，不能进行随机查找，为了能实现有序表的折半查找，尚需对记录进行重新排列。10.2插入排序插入排序1.我们都能理解，优秀排序算法的首要条件就是2.于是人们想了许许多多的排序办法，目的就是为了提高排序的速度。3.而在很长的时间里，众人发现尽管各种排序算法花样繁多，但时间复杂度都是O(n2)，似乎没法超越了。4.计算机学术界充斥着“排序算法不可能突破O(n2)”的声音？速度10.2插入排序插入排序终于有一天，当一位科学家发布超越了O(n2)新排序算法后，紧接着就出现了好几种可以超越O(n2)的排序算法，并把内排序算法的时间复杂度提升到了O(nlog2n)。“不可能超越O(n2)”彻底成为了历史。v希尔希尔排序排序10.2插入排序插入排序基本思想：先将整个待排记录序列分割成若干子序列,分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。技巧：子序列的构成不是简单地“逐段分割”，而是将相隔某个增量dk的记录组成一个子序列,让增量dk逐趟缩短（例如依次取5,3,1），直到dk1为止。优点：让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多。312345665499725251321234562525136549971123456132525654997123456132525496597增量3增量2增量1希尔排序过程v希尔希尔排序排序10.2插入排序插入排序38例：关键字序列T=(49,38,65,97,76,13,27,49*,55,04)请写出希尔排序的具体实现过程。0123456789104938659776132749*5504初态第1趟(dk=5)第2趟(dk=3)第3趟(dk=1)4913134938276549*975576042738 65 49*9755135576045513270427044949*4949*763876 65 65 9797551327044949*3876 65 9713 27 0449*76 97 ri算法分析：开始时dk 的值较大，子序列中的对象较少，排序速度较快；随着排序进展，dk 值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。v希尔排序算法描述希尔排序算法描述10.2插入排序插入排序voidShellInsert(SqList&L,intdk)/一趟希尔插入排序/1.前后记录位置的增量是dk；/2.L.r0只是暂存单元，不是哨兵。当j=0时，插入位置已找到for(i=dk+1;i=L.length;+i)if(L.ri.key0&(L.r0.keyL.rj.key);j-=dk)L.rj+dk=L.rj;/记录后移，查找插入位置L.rj+dk=L.r0;/插入/ShellInsertv希尔排序算法描述希尔排序算法描述10.2插入排序插入排序voidShellSort(SqList&L,intdlta,intt)/按增量序列dlta0.t-1对顺序表L作希尔排序for(k=0;k1;i-)/i表示趟数，最多n-1趟flag=0;/开始时元素未交换for(intj=2;j=i;j+)if(RjRj-1)/发生逆序temp=Rj;Rj=Rj-1;Rj-1=temp;flag=1;if(flag=0)return;/Bubblesortv冒泡排序算法分析冒泡排序算法分析10.3交换排序交换排序正序：只需进行一趟排序，在排序过程中进行n-1次关键字间的比较，且不移动记录；时间复杂度为O(n)。逆序：需要进行n-1趟排序，需要进行n(n-1)/2次比较，并作等数量级的记录移动。总的时间复杂度为O(n2)。起泡排序方法是稳定的。适合于数据较少的情况。v快速快速排序排序10.3交换排序交换排序背景起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小1。试设想：若能在经过一趟排序，使无序序列的长度缩小一半，则必能加快排序的速度。v快速快速排序排序10.3交换排序交换排序(1)基本思想通过一趟排序将待排序列以枢轴为标准划分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分进行快速排序，以达到整个序列有序。通常取第一个记录的值为基准值或枢轴。v快速快速排序排序10.3交换排序交换排序(2)具体做法附设两个指针low和high，初值分别指向第一个记录和最后一个记录，设枢轴为key；1.从high所指位置起向前搜索，找到第一个不大于基准值的记录与枢轴记录相互交换；2.从low所指位置起向后搜索，找到第一个不小于基准值的记录与枢轴记录相互交换。3.重复这两步直至low=high为止。v快速快速排序排序10.3交换排序交换排序lowhigh设Rs=52为枢轴例：5252 49 80 36 14 58 61 97 23 75high23lowlow80highhighhighhigh14lowlow52v一一趟快速排序算法描述趟快速排序算法描述10.3交换排序交换排序intPartition(ElemR,intlow,inthigh)R0=Rlow;pivotkey=Rlow.key;while(lowhigh)/从两端交替向中间扫描while(low=pivotkey)-high;Rlow=Rhigh;/将比枢轴记录小的移到低端while(lowhigh&Rlow.key=pivotkey)+low;Rhigh=Rlow;/将比枢轴记录大的移到高端Rlow=R0;/枢轴记录到位returnlow;/返回枢轴位置/Partitionv快速排序快速排序算法算法过程过程10.3交换排序交换排序无序的记录序列无序记录子序列(1)无序子序列(2)枢轴 一次划分 分别进行一趟快速排序 有序的记录序列 v快速快速排序算法描述排序算法描述10.3交换排序交换排序voidQSort(ElemR,intlow,inthigh)/对序列Rlow.high进行快速排序if(lowhigh-1)/长度大于1pivot=Partition(L,low,high);/将Rlow.high一分为二QSort(L,low,pivot-1);/对低子表递归排序，pivo是枢轴QSort(L,pivot+1,high);/对高子表递归排序/QSortvoidQuickSort(ElemR,intn)/对记录序列进行快速排序对记录序列进行快速排序QSort(R,1,n);/QuickSort076，129，256，438，301，694，742，751，863，937076，129，256，301，301，694，742，751，863，937076，129，256，751751，937，863，742，694，301，438076，129，256，438，301，694，742，694，863，937256，301，751，129，937，863，742，694，076，438例：以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，写出执行快速算法的各趟排序结束时，关键字序列的状态。原始序列：256，301，751，129，937，863，742，694，076，438第1趟第2趟第3趟第4趟要求模拟算法实现步骤256256076076301301129129751751256256751751438438076，129，256，301，438，694，742，751，863，937时间效率：O(nlog2n)因为每趟确定的元素呈指数增加空间效率：O(log2n)因为算法的递归性，要用到栈空间稳定性：不稳定因为可选任一元素为支点。v快速快速排序算法详细分析排序算法详细分析10.3交换排序交换排序可以证明，函数Quicksort的平均计算时间是O(nlog2n)。实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数(新的low和high)。最大递归调用层次数与递归树的深度一致，理想情况为log2(n+1)。因此，要求存储开销为O(log2n)。v快速快速排序算法详细分析排序算法详细分析10.3交换排序交换排序最好情况：如果每次划分对一个对象定位后，该对象的左侧子序列与右侧子序列的长度相同，则下一步将是对两个长度减半的子序列进行排序，这是最理想的情况。此时，快速排序的趟数最少。最坏情况：即待排序对象序列已经按其关键码从小到大排好序的情况下，其递归树成为单支树，每次划分只得到一个比上一次少一个对象的子序列。这样，必须经过n-1趟才能把所有对象定位，而且第i趟需要经过n-i次关键码比较才能找到第i个对象的安放位置，总的关键码比较次数将达到n2/2v快速排序是否快速排序是否真的比任何排序算法都快？真的比任何排序算法都快？10.3交换排序交换排序设每个子表的支点都在中间（比较均衡），则：第1趟比较，可以确定1个元素的位置；第2趟比较（2个子表），可以再确定2个元素的位置；第3趟比较（4个子表），可以再确定4个元素的位置；第4趟比较（8个子表），可以再确定8个元素的位置；只需log2n1趟便可排好序。基本上是！因为每趟可以确定的数据元素是呈指数增加的！而且，每趟需要比较和移动的元素也呈指数下降，加上编程时使用了交替逼近技巧，更进一步减少了移动次数，所以速度特别快。vnlogn算法算法10.3交换排序交换排序voidQSort(ElemR,intlow,inthigh)/对序列Rlow.high进行快速排序if(lowhigh-1)/长度大于1pivot=Partition(L,low,high);/将Rlow.high一分为二QSort(L,low,pivot-1);/对低子表递归排序，pivo是枢轴QSort(L,pivot+1,high);/对高子表递归排序/QSortvoidQuickSort(ElemR,intn)/对记录序列进行快速排序对记录序列进行快速排序QSort(R,1,n);/QuickSortvnlogn算法算法1.设T(n)为一个规模为n的问题的运行时间；2.假如我们把原问题分解为2个子问题，每一个的大小是原问题的1/2；3.对于含有n个元素的数组，划分的时间代价为O(n)10.3交换排序交换排序T(n)=2T(n/2)+O(n)vnlogn算法算法10.3交换排序交换排序10.3交换排序交换排序v二叉树二叉树的性质的性质6.2二叉树二叉树性质4：具有n个结点的完全二叉树的高度为log2n+1证明：设完全二叉树的高度为k，则有(2k-1-1)n(2k-1)或2k-1 n2k两边取对数k-1log2nk因为k是整数，所以k=log2n+1v快速排序算法平均快速排序算法平均情况分析情况分析1.设T(n)为一个规模为n的问题的运行时间；2.假如我们把原问题分解为2个子问题，每一个的大小是T(9n/10)和T(n/10)；3.对于含有n个元素的数组，划分的时间代价为O(n)10.3交换排序交换排序T(n)=T(9n/10)+T(n/10)+O(n)v快速排序算法平均情况分析快速排序算法平均情况分析10.3交换排序交换排序v快速排序算法平均快速排序算法平均情况分析情况分析1.看上去9:1很不平行的划分，执行时间O(nlogn)2.原因在于，任何一种常熟比例的划分，都会产生O(logn)的递归树，且每一层的代价为O(n)，因此总的运行时间都是O(nlogn)10.3交换排序交换排序武汉科技大学Wuhan University of Science and Technology