数据结构第九章内部排序

1、第九章 内部排序将n个性质相同的数据元素按关键字值从小到大或从大到小排为有序序列。F外部排序F内部排序当待排数据元素的数量较少时，可将其一次全部调入内存进行排序，即称内部排序。当待排数据元素的数量较大时，在排序过程中尚需对外存进行访问，则称外部排序。F排序一、基本术语注意当按次关键字进行排序时，由于可能存在关键字值相同的元素，因而排序结果不惟一。一、基本术语举例原序列排序结果学号姓名成绩1王云672李永强833刘小玲724赵祥925陈晓壮83学号姓名成绩1王云673刘小玲722李永强835陈晓壮834赵祥92排序方法A必然稳定的排序方法举例原序列排序结果学号姓名成绩1王云672李永强833刘小

2、玲724赵祥925陈晓壮83学号姓名成绩1王云673刘小玲725陈晓壮832李永强834赵祥92排序方法B可能非稳定的排序方法F插入排序按排序原则分F交换排序F选择排序F归并排序F计数排序二、内部排序法分类F简单的内部排序法O(n2)按排序的时间复杂度分F先进的内部排序法O(nlogn)F基数排序法O(dn)二、内部排序法分类F折半插入排序法F2路插入排序法F表插入排序法F直接插入排序法F希尔排序法三、插入排序法设对数据元素序列R1,R2,Rn进行排序，则：仅含R1的序列是长度为1的按关键字值有序的序列；方法举例4938659776132749012345678初始1、直接插入排序法依次逐个将

3、Ri（i=2,3,n）插入已有的按关键字值有序的序列，并使插入完成后的序列仍按关键字值有序。方法举例4938659776132749012345678一趟比较次数移动次数1次1次2次3次1、直接插入排序法依次逐个将Ri（i=2,3,n）插入已有的按关键字值有序的序列，并使插入完成后的序列仍按关键字值有序。方法举例3849659776132749012345678二趟比较次数移动次数1次1、直接插入排序法依次逐个将Ri（i=2,3,n）插入已有的按关键字值有序的序列，并使插入完成后的序列仍按关键字值有序。方法举例3849659776132749012345678三趟比较次数移动次数1次1、直接插

4、入排序法依次逐个将Ri（i=2,3,n）插入已有的按关键字值有序的序列，并使插入完成后的序列仍按关键字值有序。方法举例3849659776132749012345678四趟比较次数移动次数1次1次2次3次2次1、直接插入排序法依次逐个将Ri（i=2,3,n）插入已有的按关键字值有序的序列，并使插入完成后的序列仍按关键字值有序。方法举例3849657690132749012345678五趟比较次数移动次数1次1次2次3次2次3次4次4次5次5次6次7次1、直接插入排序法依次逐个将Ri（i=2,3,n）插入已有的按关键字值有序的序列，并使插入完成后的序列仍按关键字值有序。方法举例133849657

5、6972749012345678六趟比较次数移动次数1次1次2次3次2次3次4次4次5次5次6次6次1、直接插入排序法依次逐个将Ri（i=2,3,n）插入已有的按关键字值有序的序列，并使插入完成后的序列仍按关键字值有序。方法举例1327384965769749012345678七趟比较次数移动次数1次1次2次3次2次3次4次4次5次1、直接插入排序法4927存储结构设计stst384965977613021345678#define LENGTH 8typedef ElemType SortTableLENGTH+1;1、直接插入排序法算法void InsertSort(SortTable &

6、amp;st)for(i=2;i=1 & stj.keyst0.key)if(sti.keysti-1.key)stj+1=stj;j-;1、直接插入排序法/if/InsertSortstj+1=st0;1、直接插入排序法元素的移动，最少次，最多次。最多次；算法分析插入第i个数据元素时，关键字值间的比较最少次，况下需进行次关键字值间的比较，次元素的移动；在最坏情况下则需进行次关键字值间的比较，次元素的移动。若待排序列中有n个数据元素，则要完成排序在最好情1i-10i+1n-10(1+2+n-1)=n(n-1)/2(3+4+n+1)=(n-1)(n+4)/21、直接插入排序法并需要的辅助

7、存储空间。算法时间复杂度在最好时为，最坏时为，可见直接插入排序法在或时效率较高。O(n)O(n2)一个元素待排数据元素序列已基本有序待排数据元素个数较少1、直接插入排序法改进思路F减少关键字值间的比较次数F减少数据元素的移动次数F尽可能创造待排元素序列基本有序或是待排数据元素个数较少的场景1、直接插入排序法在直接插入排序法中，关键字值间的比较主要用于确定元素的插入位置。由于插入第i个元素时，前i-1个元素已经思路有序，所以可用折半查找确定其插入位置。2、折半插入排序法举例3849657697132749012345678六趟比较次数移动次数1次1次2次3次2次l lh hm m3次4次5次6次

8、7次2、折半插入排序法与直接插入排序法相比，折半插入排序法减少了关键字值间比较的次数，但没有减少元素移动的次数，因此算法的算法分析时间复杂度仍为O(n2)，并仍需一个元素的辅助存储空间。2、折半插入排序法直接插入排序法在待排数据元素个数较少时效率较高，若先在待排元素中选择一个R作为参照，然后把关键字值大思路于R的插入在其后，关键字值小于R的插入在其前，则能缩短元素所插入的表的长度，从而减少排序过程中关键字值的比较次数和元素的移动次数。3、二路插入排序法设置辅助数组sortedn，将R1保存至sorted0；方法设对数据元素序列R1,R2,Rn进行排序，则：关键字值大于R1的插入在其后，关键字值

9、小于R1的插入在其前。以R1为参照，依次逐个有序插入Ri（i=2, 3,n），其中3、二路插入排序法举例493865977613274901234567初始493865977613274901234567sortedf fr r一趟3、二路插入排序法举例493865977613274901234567初始493865977613274901234567f fr r二趟sorted3、二路插入排序法举例493865977613274901234567初始493865977613274901234567f fr r三趟sorted3、二路插入排序法举例49386597761327490123456

10、7初始493865977613274901234567f fr r四趟sorted3、二路插入排序法举例493865977613274901234567初始493865977613274901234567f fr r五趟sorted3、二路插入排序法举例493865977613274901234567初始493865977613274901234567f fr r六趟sorted3、二路插入排序法举例493865977613274901234567初始493865977613274901234567f fr r七趟sorted3、二路插入排序法与直接插入排序法相比，二路插入排序法中关键字值间的

11、比较次数及元素的移动次数平均可减少一半左右，但时间算法分析复杂度仍为O(n2)，且需n个元素的辅助空间。当R1的关键字值在待排元素中为最大值或最小值时，二路插入排序法退化为直接插入排序法。3、二路插入排序法如果在插入的过程中不改变数据元素的存储位置，则不需要进行元素的移动，但应另外设法记录各待排元素间依关思路键字值从小到大或从大到小的先后次序。4、表插入排序法设置辅助数组addrn+1，其中addr0记录结果序列中排方法在第一位的数据元素的下标，addri（i=1,2,n）记录设对数据元素序列R1,R2,Rn进行排序，则：结果序列中排在Ri的下一位的数据元素的下标，若结果序仅含R1的序列是长度

12、为1的按关键字值有序的序列，所以令addr0=1，addr1=0；列中最后一个元素为Rj，则令addrj=0；4、表插入排序法入过程中不对数据元素进行移动，而只改变addr数组中相应位置的值。的序列，并使插入完成后的序列仍按关键字值有序，在插依次逐个将Ri（i=2,3,n）插入已有的按关键字值有序4、表插入排序法举例498初始14923836549757661372701234567addr一趟804981492383654975766137274、表插入排序法举例498初始14923836549757661372701234567addr二趟8049814923836549757661372

13、74、表插入排序法举例498初始14923836549757661372701234567addr三趟804981492383654975766137274、表插入排序法举例498初始14923836549757661372701234567addr四趟804981492383654975766137274、表插入排序法举例498初始14923836549757661372701234567addr五趟804981492383654975766137274、表插入排序法举例498初始14923836549757661372701234567addr六趟804981492383654975766

14、137274、表插入排序法举例498初始14923836549757661372701234567addr七趟804981492383654975766137274、表插入排序法举例498初始14923836549757661372701234567addr八趟804981492383654975766137274、表插入排序法举例498初始14923836549757661372701234567addr80812345674、表插入排序法与直接插入排序法相比，表插入排序法通过修改2n次指针值代替了数据元素的移动，但未减少关键字值间的比较次算法分析数，时间复杂度仍为O(n2)，且需长度为n的

15、整型辅助数组。经表插入排序所得的有序链表只能进行顺序查找，若要进行折半查找，则需对表中元素进行重排。4、表插入排序法插入排序，待整个序列中的元素基本有序时，再对全体元素思路进行一次直接插入排序。先将整个待排元素序列分割成若干子序列分别进行直接这里子序列的构成不是简单地逐段分割，而是将相隔某个“增量”的元素组成为一个子序列。5、希尔排序法举例设增量序列为5,3,1。4938659776132749012345678初始55904105、希尔排序法举例设增量序列为5,3,1。4938659776132749012345678第一趟：增量为555904105、希尔排序法举例设增量序列为5,3,1。1

16、338659776492749012345678第一趟：增量为555904105、希尔排序法举例设增量序列为5,3,1。1327659776493849012345678第一趟：增量为555904105、希尔排序法举例设增量序列为5,3,1。1327659776493849012345678第一趟：增量为555904105、希尔排序法举例设增量序列为5,3,1。1327655576493849012345678第一趟：增量为597904105、希尔排序法举例设增量序列为5,3,1。1327655504493849012345678第二趟：增量为397976105、希尔排序法举例设增量序列为5,

17、3,1。1327653804495549012345678第二趟：增量为397976105、希尔排序法举例设增量序列为5,3,1。1304653827495549012345678第二趟：增量为397976105、希尔排序法举例设增量序列为5,3,1。1304653827495549012345678第三趟：增量为197976105、希尔排序法举例设增量序列为5,3,1。0413653827495549012345678第三趟：增量为197976105、希尔排序法举例设增量序列为5,3,1。0413653827495549012345678第三趟：增量为197976105、希尔排序法在希尔排序

18、中，关键字较小的元素能跳跃式地前移，从而在进行最后一趟增量为1的插入排序时，序列已基本有序，算法分析只要进行少量的比较和移动即可完成排序，因而时间复杂度比直接插入排序低。希尔排序的时间复杂度与所取增量序列有关。增量序列可有各种取法，但各增量值间应无除1之外的公因子，且最后一个增量值必为1。5、希尔排序法F快速排序法F起泡排序法四、交换排序方法对相邻的两个数据元素的关键字值进行比较，若为逆序，方法设对数据元素序列R1,R2,Rn进行排序，则：一趟排序完成后，关键字值最大的数据元素排在了最后，如此重复n-1次，即可完成排序。则交换；1、起泡排序法举例498初始1492383654975766137

19、27一趟比较次数移动次数1次3次6次9次2次3次12次4次15次5次6次7次1、起泡排序法举例978初始138249365476513627749一趟比较次数移动次数1次3次6次9次2次3次4次5次6次二趟15次7次1、起泡排序法三趟二趟举例978初始138249365413527649776一趟比较次数移动次数1次3次6次9次2次3次4次5次15次7次9次6次1、起泡排序法四趟二趟举例978初始138249313427549665776一趟比较次数移动次数1次3次6次2次3次4次15次7次9次6次三趟9次5次1、起泡排序法五趟二趟举例978初始138213327449549665776一趟比

20、较次数移动次数1次3次6次2次3次15次7次9次6次三趟9次5次比较次数移动次数四趟6次4次1、起泡排序法六趟二趟举例978初始113227338449549665776一趟比较次数移动次数1次2次15次7次9次6次三趟9次5次比较次数移动次数四趟6次4次五趟6次3次1、起泡排序法元素的移动，最少次，最多次。最多次；算法分析在第i趟起泡排序中，关键字值间的比较最少次，况下需进行次关键字值间的比较，次元素的移动；在最坏情况下则需进行次关键字值间的比较，次元素的移动。若待排序列中有n个数据元素，则要完成排序在最好情n-in-i03(n-i)n-10(1+2+n-1)=n(n-1)/23(1+2+n

21、)=3n(n-1)/21、起泡排序法并需要的辅助存储空间。算法时间复杂度在最好时为，最坏时为，O(n)O(n2)一个元素1、起泡排序法若s=t ，即序列中仅一个元素，则排序完成；方法设对数据元素序列Rs,Rt进行排序，则：若st，则以Rs为枢轴进行一趟快速排序：493865977613274912345678初始02、快速排序法键字值的元素，若该元素在枢轴之后，则交换两者位置；493865977613274912345678一趟h hl l令low=s，high=t；从high所指位置开始向前找第一个关键字值小于枢轴关键02、快速排序法值的元素，若该元素在枢轴之前，则交换两者位置；493865

22、977613274912345678一趟h hl l从low所指位置开始向后找第一个关键字值大于枢轴关键字02、快速排序法493865977613274912345678一趟h hl l0如此重复直至high=low，则本趟快排完成；2、快速排序法493865977613274912345678二趟h hl l0分别对枢轴元素之前和之后的序列进行快排。2、快速排序法493865977613274912345678二趟h hl l0分别对枢轴元素之前和之后的序列进行快排。2、快速排序法493865977613274912345678三趟h hl l0分别对枢轴元素之前和之后的序列进行快排。2、快

23、速排序法则可减少元素移动次数。改进在快速排序的过程中，若用一辅助空间暂存枢轴元素，493865977613274912345678初始0h hl l2、快速排序法4927存储结构设计stst384965977613021345678#define LENGTH 8typedef ElemType SortTableLENGTH+1;2、快速排序法算法int Partition(SortTable &st,int low,int high)/以stlow为枢轴，对stlow至sthigh完成一趟快排st0=stlow;/暂存枢轴元素while(lowhigh)while(low=st0.

24、key)-high;/返回本趟快排完成后枢轴元素所在位置的下标stlow=sthigh;2、快速排序法sthigh=stlow;/whilereturn low;/Partitionstlow=st0;/枢轴元素到位while(lowhigh&stlow.key=st0.key)+low;2、快速排序法if (lowhigh)p=Partition(L,low,high);/完成一趟快排QSort(st,p+1,high);/ifQSort(st,low,p-1);void QSort(SortTable &st,int low,int high)/QSort2、快速排序法QS

25、ort(st,1,LENGTH);/QuickSortvoid QuickSort(SortTable &st)2、快速排序法快速排序法平均时间复杂度为O(knlogn)，经验证明，在所有时间复杂度处于同数量级的内部排序算法中，快速排算法分析序法的常数因子k最小。若待排元素序列初始即为正序或基本有序，快速排序法将退化为起泡排序法，时间复杂度达O(n2)。2、快速排序法F树形选择排序法F简单选择排序法F堆排序法五、选择排序方法n-i+1 (i=1,n-1) 个元素中选择一个关键字值最小的，方法设对数据元素序列R1,R2,Rn进行排序，则每趟在排序完成。并将它与序列中的第i个元素交换，如此

26、重复n-1次，则1、简单选择排序法举例4938659776132749012345678初始1、简单选择排序法举例4938659776132749012345678一趟minmini i比较次数移动次数1次2次3次4次5次6次7次3次1、简单选择排序法举例1338659776492749012345678二趟minmini i比较次数移动次数1次2次3次4次5次6次3次1、简单选择排序法举例1327659776493849012345678三趟minmini i比较次数移动次数1次2次3次4次5次3次1、简单选择排序法举例1327389776496549012345678四趟minmini i

27、比较次数移动次数1次2次3次4次3次1、简单选择排序法举例1327384976976549012345678五趟minmini i比较次数移动次数1次2次3次3次1、简单选择排序法举例1327384976976549012345678六趟minmini i比较次数移动次数1次2次3次1、简单选择排序法举例1327384976659749012345678七趟minmini i比较次数移动次数1次3次1、简单选择排序法举例1327384997657649012345678七趟1、简单选择排序法键字值间的比较，次元素的移动。次元素的移动；元素的移动，最少次，最多次。最多次；算法分析在第i趟简单选择

28、排序中，关键字值间比较最少 次，况下需进行次关键字值间的比较，在最坏情况下则需进行次关若待排序列中有n个数据元素，则要完成排序在最好情n-in-i030n(n-1)/23(n-1)(n-1)+2+1=n(n-1)/21、简单选择排序法空间。算法的时间复杂度为O(n2)，并需要一个元素的辅助存储1、简单选择排序法先对n个元素的关键字值进行两两比较，然后在其中的方法设对数据元素序列R1,R2,Rn进行排序，则：出关键字值最小的元素，该过程可用一棵有n个叶子结 n/2 个较小者间再进行两两比较，如此重复，直至选点的完全二叉树表示；2、树形选择排序法举例493865977613274901234567

29、8初始2、树形选择排序法举例4938659776132749比较次数移动次数1次2次3次4次5次6次7次i i38651327381313minmin4938659776132749012345678一趟2、树形选择排序法中的对应关键字值改为，并修改从该结点到根的路径上方法通过交换，使关键字值最小的元素到位，然后将叶子结点如此重复n-1次，则排序完成。各结点的值，以选出关键字值次小的数据元素；2、树形选择排序法举例4938659776132749比较次数移动次数7次3次i i38651327381313minmin4938659776132749012345678一趟2、树形选择排序法举例49

30、38659776132749比较次数移动次数i i386513273813131338659776492749012345678二趟1次2次3次3次762727minmin2、树形选择排序法举例49386597762749比较次数移动次数i i386576273827271327659776493849012345678三趟1次2次3次3次minmin4949382、树形选择排序法举例493865977649比较次数移动次数i i386576493849381327389776496549012345678四趟1次2次3次3次minmin4949492、树形选择排序法举例4965977649比

31、较次数移动次数i i496576494949491327384976976549012345678五趟1次2次3次3次minmin65492、树形选择排序法举例65977649比较次数移动次数i i6576496549491327384949976576012345678六趟1次2次3次3次minmin76652、树形选择排序法举例659776比较次数移动次数i i65766576651327384949659776012345678七趟1次2次3次3次minmin9797762、树形选择排序法由此可见，树形选择排序的时间复杂度为O(nlogn)，最坏情况下则需进行3次元素移动。而在其后的每趟

32、树形选择排序中，关键字值间只需进行算法分析在第1趟树形选择排序中，关键字值间需进行n-1次比较，每趟树形选择排序，在最好情况下需进行0次元素移动， log2n 次比较。所需辅助空间为(2n-1)+1个。2、树形选择排序法将含n个待排元素的初始序列看作一棵完全二叉树的层序方法设对数据元素序列R1,R2,Rn进行排序，则：至第1个元素止，逐一进行“筛选”；遍历序列，在这棵完全二叉树上，从第 n/2 个元素起，3、堆排序法将该元素的关键字值与其左、右孩子的关键字值进在完全二叉树上对一个元素进行“筛选”，就是将该元素与关键字值较大的孩子交换。行比较，如果其关键字值不是三者之中最大的，则如此循环，直至该

33、元素成为叶子结点或其左、右孩子的关键字值都不比它大为止。举例4938659776132749012345678初始3、堆排序法举例0491382653974765136277498一趟3、堆排序法举例比较次数移动次数1次2次3次4次5次6次7次4913826539747651362774983次6次8次9次12次9次10次第一轮“筛选”完成后，初始大顶堆建成。3、堆排序法进行“筛选”，使剩余元素重又构成一个大顶堆；方法将堆顶元素与该堆最后一个元素交换，并对新的堆顶元素如此重复n-1次，则排序完成。3、堆排序法举例比较次数移动次数1次2次3次4次9717626534944951362773883

34、次6次9次二趟3、堆排序法举例比较次数移动次数1次2次3次7614926533844951362779783次6次三趟3、堆排序法举例比较次数移动次数1次2次3次6514922733844951367679783次6次四趟4次3、堆排序法举例比较次数移动次数1次2次3次4914922733841356567679783次6次五趟9次3、堆排序法举例比较次数移动次数1次2次4913822731344956567679783次6次六趟3、堆排序法举例比较次数移动次数1次3811322734944956567679783次6次七趟3、堆排序法举例1312723834944956567679783、堆

35、排序法4927存储结构设计stst384965977613021345678#define LENGTH 8typedef ElemType SortTableLENGTH+1;3、堆排序法算法void HeapAdjust(SortTable &st,int s,int m)/在sts.m中，对sts进行筛选k=s;j=2*k;/k为待筛选元素下标，j为k的左孩子下标while(j=m)/待筛选元素有左孩子，即非叶子结点st0=sts;/暂存待筛选元素3、堆排序法if(jstj.key)/右孩子键值更大stk=stj+1;/右孩子上移elsestk=stj;/左孩子上移k=j;/待筛

36、选元素的新位置k=j+1;/待筛选元素的新位置if(stj.keyst0.key)/左孩子键值较大3、堆排序法if(jst0.key)/右孩子键值较大stk=stj+1;/右孩子上移/ifelse break;/左、右孩子的键值都比待筛选元素小k=j+1;/待筛选元素的新位置else/左孩子键值不大j=2*k;/进行下一轮筛选/while/HeapAdjust3、堆排序法for(i=LENGTH/2;i=1;-i)HeapAdjust(st,i,LENGTH);st1=sti;sti=st0;/一个元素到位HeapAdjust(st,1,i-1);/对新的堆顶元素做一轮筛选for(i=LENG

37、TH;i1;-i)st0=st1;void HeapSort(SortTable &st)/HeapSort3、堆排序法堆排序法的时间主要用于反复筛选，除构造初始堆外，每趟排序进行一轮筛选，筛选时进行的关键字比较次数最算法分析坏情况下为(完全二叉树的高度-1)*2。若有n个待排元素，则完全二叉树的高度为log2n+1，所以在最坏情况下，堆排序法的时间复杂度也为O(nlogn)。另外还需一个元素的辅助空间。3、堆排序法F多路归并排序法F二路归并排序法六、归并排序方法对数据元素序列R1,R n/2进行排序；方法设对数据元素序列R1,R2,Rn进行排序，则：对由和得到的有序序列进行归并。对数

38、据元素序列Rn/2+1 , Rn进行排序；二路归并排序法举例493865977613274901234567初始1、二路归并排序法举例01234567一趟1、二路归并排序法比较次数移动次数1次2次3次4次1次2次3次49386597761327494次5次6次7次8次举例01234567二趟1、二路归并排序法比较次数移动次数1次2次3次4次1次2次3次38496597137627494次5次6次7次8次5次举例01234567三趟1、二路归并排序法比较次数移动次数1次2次3次4次1次2次3次38496597132749764次5次6次7次8次5次6次7次4927存储结构设计stst384965

39、977613021345678#define LENGTH 8typedef ElemType SortTableLENGTH+1;二路归并排序法对st1.m排序，m=LENGTH/2；思路对已有序的st1.m和stm+1.LENGTH归并。对stm+1.LENGTH排序；void MSort(SortTable st,int i,int j)void Merge(SortTable st,int i,int j,int k)二路归并排序法4927stst384965977613021345678思路细化void MSort(SortTable st,int i,int j)MSort(st,

40、i,(i+j)/2);若i=j，则排序完成；MSort(st,(i+j)/2+1,j);Merge(st,i,(i+j)/2,j)。二路归并排序法4927stst384965977613021345678设置辅助数组temp；思路细化void Merge(SortTable st,int i,int j,int k)令x=i，y=j+1，z=1；tempxyz比较stx和sty，较小者赋给tempz，并使相应指针下移；重复直至一表结束；将另一表中剩余元素全部复制到temp；7649stst493865971327021345678将temp复制到st。算法void MSort(SortTable st,int i,int j)MSort(st,i,(i+j)/2);if (i=j) return;MSort(st,(i+j)/2+1,j);Merge(st,i,(i+j)/2,j);/MSort二路归并排序法void Merge(SortTable st,int i,int j,int k)算法x=i;y=j+1;z=1;while(x=j&y=k)if (stx.key=sty.key) tempz+=stx+;else tempz+=sty+;/whilewhile (x=j) tempz+=stx+;while (y=k)