第10章--内排序

第10章内排序10.6基数排序10.1排序的基本概念10.2插入排序10.3交换排序10.4选择排序10.5归并排序10.7各种内排序方法的比较和选择10.1排序的基本概念所谓排序，是要整理表中的记录，使之按关键字递增（或递减）有序排列。其确切定义如下：输入：n个记录,R0,R1,…,Rn-1,其相应的关键字分别为k0,k1,…,kn-1。输出：Ri,0,Ri,1,…,Ri,n-1,使得ki,0≤ki,1≤…≤ki,n-1(或ki,0≥ki,1≥…≥ki,n-1)。本章仅考虑递增排序当待排序记录的关键字均不相同时，排序的结果是惟一的,否则排序的结果不一定唯一。如果待排序的表中,存在有多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是稳定的；反之,若具有相同关键字的记录之间的相对次序发生变化,则称这种排序方法是不稳定的。在排序过程中，若整个表都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内排序；反之，若排序过程中要进行数据的内、外存交换，则称之为外排序。算法的稳定性内排序和外排序内排序的基本方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。经过一趟排序有序序列区无序序列区有序序列区无序序列区正序和反序若待排序的表中元素已按关键字排好序，称此表中元素为正序；反之，若待排序的表中元素的关键字顺序正好和排好序的顺序相反，称此表中元素为反序。排序的分类根据排序算法是否基于关键字的比较，将排序算法分为基于比较的排序算法和不基于比较的排序算法。像插入排序、交换排序、选择排序和归并排序都是基于比较的排序算法；而基数排序是不基于比较的排序算法。待排序的顺序表类型的类型定义如下：typedefintKeyType;//定义关键字类型typedefstruct//记录类型{KeyTypekey;//关键字项InfoTypedata;//其他数据项,类型为InfoType}RecType;//排序的记录类型定义存放数据的结构：10.2插入排序插入排序的基本思想是：每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子表中的适当位置,直到全部记录插入完成为止。两种插入排序方法：（1）直接插入排序（含二分插入排序）（2）希尔排序10.2.1直接插入排序假设待排序的记录存放在数组R[0..n-1]中，排序过程的某一中间时刻，R被划分成两个子区间R[0..i-1]和R[i..n-1]，其中：前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨称其为无序区。直接插入排序的基本操作是将当前无序区的第1个记录R[i]插入到有序区R[0..i-1]中适当的位置上，使R[0..i]变为新的有序区。这种方法通常称为增量法，因为它每次使有序区增加1个记录。R[0]R[i-1]有序区R[i]R[n-1]无序区一趟排序R[0]R[i-1]R[i]R[i+1]R[n-1]有序区无序区R[0]jR[i]j=i-1插入位置在有序区中插入R[i]的过程voidInsertSort(RecTypeR[],intn)//对R[0..n-1]按递增有序进行直接插入排序{inti,j;RecTypetemp;for(i=1;in;i++){temp=R[i];j=i-1;//从右向左在有序区R[0..i-1]找R[i]的插入位置while(j=0&&temp.keyR[j].key){R[j+1]=R[j];//将关键字大于R[i].key的记录后移j--;}R[j+1]=temp;//在j+1处插入R[i]}}例10.1设待排序的表有10个记录，其关键字分别为{9,8,7,6,5,4,3,2,1,0}。说明采用直接插入排序方法进行排序的过程。初始关键字9876543210i=1[89]76543210i=2[789]6543210i=3[6789]543210i=4[56789]43210i=5[456789]3210i=6[3456789]210i=7[23456789]10i=8[123456789]0i=9[0123456789]对于直接插入排序：最好的情况（关键字在记录序列中顺序有序）：“比较”的次数：最坏的情况（关键字在记录序列中逆序有序）：“比较”的次数：1111nni2(n-1)“移动”的次数：“移动”的次数：2)1(11nnini2)4)(1()2(11nnini总的平均比较和移动次数约为)(2)4)(1()2()222(21111nOnniiinini直接插入排序算法稳定性证明：另外，当ij且R[i].key=R[j].key时，本算法将R[i]插入在R[j]的后面，使R[i]和R[j]的相对位置保持不变，所以直接插入排序是一种稳定的排序方法。{…R[j]…}R[i]…有序区R[i]插入在R[j]的后面10.2.2折半插入排序查找采用折半查找方法，称为二分插入排序或折半插入排序。voidInsertSort1(RecTypeR[],intn){inti,j,low,high,mid;RecTypetmp;for(i=1;in;i++){tmp=R[i];//将R[i]保存到tmp中low=0;high=i-1;while(low=high)//在R[low..high]中查找插入的位置{mid=(low+high)/2;//取中间位置if(tmp.keyR[mid].key)high=mid-1;//插入点在左半区elselow=mid+1;//插入点在右半区}for(j=i-1;j=high+1;j--)//记录后移R[j+1]=R[j];R[high+1]=tmp;//插入}}折半插入排序的元素移动次数与直接插入排序相同，不同的仅是变分散移动为集合移动。在R[0..i-1]中查找插入R[i]的位置，折半查找的平均关键字比较次数为log2(i+1)-1，平均移动元素的次数为i/2+2，所以平均时间复杂度为：)()221)1(log(2112nOiini就平均性能而言，折半查找优于顺序查找，所以折半插入排序也优于直接插入排序。折半插入排序的空间复杂度为O(1)。10.2.3希尔排序希尔排序也是一种插入排序方法,实际上是一种分组插入方法。基本思想：先取定一个小于n的整数d1作为第一个增量，把表的全部记录分成d1个组，所有距离为d1的倍数的记录放在同一个组中，在各组内进行直接插入排序；然后取第二个增量d2（＜d1），重复上述的分组和排序，直至所取的增量dt=1（dtdt-1…d2d1），即所有记录放在同一组中进行直接插入排序为止。将记录序列分成若干子序列，分别对每个子序列进行插入排序。其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。例如：将n个记录分成d个子序列：{R[0]，R[d]，R[2d]，…，R[kd]}{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}…{R[d-1]，R[2d-1]，R[3d-1]，…，R[(k+1)d-1]}例如：162512304711233691831设增量d=5:112312918162536304731voidShellSort(RecTypeR[],intn)//希尔排序算法{inti,j,gap;RecTypetmp;gap=n/2;//增量置初值while(gap0){for(i=gap;in;i++)//对相隔gap位置的元素组直接插入排序{tmp=R[i];j=i-gap;while(j=0&&tmp.keyR[j].key){R[j+gap]=R[j];j=j-gap;}R[j+gap]=tmp;}gap=gap/2;//减小增量}}例10.2设待排序的表有10个记录,其关键字分别为{9,8,7,6,5,4,3,2,1,0}。说明采用希尔排序方法进行排序的过程。9876543210初始状态(连线部分为下一趟作准备)4321098765d=5(d=5执行结果)0123456789d=2(d=2执行结果)0123456789d=1(d=1执行结果)希尔排序的时间复杂度约为O(n1.3)。为什么希尔排序比直接插入排序好？例如：有10个元素要排序。希尔排序直接插入排序大约时间=102=100d=5：分为5组，时间约为5*22＝20d=2：分为2组，时间约为2*52＝50d=1：分为1组，几乎有序，时间约为10＋＋＝80希尔排序算法不稳定的反例希尔排序法是一种不稳定的排序算法。例如，若希尔排序分为两组：{3,10,7,8,20}和{5,8,2,1,6}，显然，第1组的8排列在第2组的8的后面，两组采用直接插入排序后的结果为：{3,7,8,10,20}和{1,2,5,6,8}，这样第1组的8排列到第2组的8的前面，它们的相对位置发生了改变。思考题：希尔排序中的有序区是全局有序吗？10.3交换排序交换排序的基本思想：两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。两种交换排序:（1）冒泡排序（2）快速排序10.3.1冒泡排序冒泡排序的基本思想：通过无序区中相邻记录关键字间的比较和位置的交换，使关键字最小的记录如气泡一般逐渐往上“漂浮”直至“水面”。整个算法是从最下面的记录开始，对每两个相邻的关键字进行比较,且使关键字较小的记录换至关键字较大的记录之上，使得经过一趟冒泡排序后，关键字最小的记录到达最上端，接着再在剩下的记录中找关键字次小的记录，并把它换在第二个位置上。依次类推，一直到所有记录都有序为止。一趟排序R[0]有序区无序区R[i-1]R[i]R[n-1]R[i+1]R[0]R[i]R[i-1]将无序区中最小记录放在R[i]R[i+1]R[n-1]有序区无序区voidBubbleSort(RecTypeR[],intn){inti,j;RecTypetemp;for(i=0;in-1;i++){for(j=n-1;ji;j--)//比较找本趟最小关键字的记录if(R[j].keyR[j-1].key){temp=R[j];//R[j]与R[j-1]进行交换R[j]=R[j-1];R[j-1]=temp;}}}{全局有序区}R[i]……R[n-1]用交换找最小记录放到R[i]处例10.3设待排序的表有10个记录,其关键字分别为{9,8,7,6,5,4,3,2,1,0}。说明采用冒泡排序方法进行排序的过程。初始关键字9876543210i=00987654321i=10198765432i=20129876543i=30123987654i=40123498765i=50123459876i=60123456987i=70123456798i=80123456789思考题：冒泡排序中的有序区是全局有序吗？在有些情况下，在第i（i＜n-1）趟时已排好序了，但仍执行后面几趟的比较。实际上，一旦算法中某一趟比较时不出现记录交换，说明已排好序了，就可以结束本算法。为此得到改进冒泡排序算法如下：voidBubbleSort(RecTypeR[],intn){inti,j;boolexchange;RecTypetemp;for(i=0;in-1;i++){exchange=false;for(j=n-1;ji;j--)//比较,找出最小关键字的记录if(R[j].keyR[j-1].key){temp=R[j];R[j]=R[j-1];R[j-1]=temp;exchange=true;}if(exchange==false)return;//中途结束算法}}最好的情况（关键字在记录序列中顺序有序）：只需进行一趟冒泡“比较”的次数：最坏的情况（关键字在记录序列中逆序有序）：需进行n-1趟冒泡“比较”的次数：0“移动”的次数：“移动”的次数：n-121110)n(n)in(ni2131320)n(n