软件技术基础-排序1

排序的目的是将一组任意的数据元素(或记录)序列，按照人们所需要的顺序，排列成有规律的按关键字有序的序列。如手机电话簿、目前的各种排行榜第十四章排序本章主要内容：1.排序的基本概念2.插入排序3.选择排序4.交换排序5.归并排序第十四章排序预备知识：关键字(key):通常数据对象有多个属性域，即多个数据成员组成，其中有一个属性域可用来区分对象，作为排序依据，该域即为关键字。如学生这个数据对象，关键字可以是学号或身份证号。每个数据表用哪个属性域作为关键码，要视具体的应用需要而定。1.排序的基本概念1)排序的概念：就是整理文件中的记录，将它们按照关键字值的递增或递减的顺序排列起来。假设文件中含有n个记录(R1,R2,…,Rn),它们的关键字分别为k1，k2，…，kn，我们将这n个记录重排为Ri1,Ri2,…,Rin,使得ki1≤ki2≤…≤kin(或ki1≥ki2≥…≥kin)，这就是排序。排序前：(R1,R2,…,Rn),k1，k2，…，kn(无序)排序后：(Ri1,Ri2,…,Rin)ki1≤ki2≤…≤kin(或ki1≥ki2≥…≥kin)(有序)1.排序的基本概念2)排序的稳定性：存在于文件中的记录，可能含有相同的关键字。对于关键字ki=kj的记录Ri和Rj，如果在原始文件中，Ri排在Rj之前，而排序后的文件中Ri仍然排在Rj之前，就称排序是稳定的。反之，如果排序后变成Ri排在Rj之后，就称此排序是不稳定的。1.排序的基本概念1.排序的基本概念3)排序分类–按待排序记录所在位置分：内部排序：整个排序过程都在内存中进行的排序，适用于记录文件个数不是很多的小文件。外部排序：当排序的文件很大时，以至内存不足以存放全部记录，需借助对外存进行访问的排序，适用于记录个数太多，不能一次将其全部放入内存的大文件。–内部排序按排序所用策略分：插入排序：直接插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序归并排序：2-路归并排序1.排序的基本概念4)内部排序所用的存储结构：以一维数组作为存储结构排序过程是对记录本身进行物理重排，即通过比较和判定，把记录移动合适的位置。以链表作为存储结构排序过程中无须移动记录，仅需修改指针即可，通常把这类排序称为表排序。为排序文件建立辅助表有的排序方法难以在链表上实现，此时，若仍需要避免排序过程记录的移动，可以为文件记录一个辅助表（如索引表），这样，排序过程中只需对这个辅助的表进行物理重排，而不移动记录本身。1.排序的基本概念5)排序方法的评价：执行算法所需要的时间执行算法所需要的附加空间算法本身的复杂程度排序是一种经常使用的一种运算，其所需的附加空间量一般都不大，所以排序的时间代价是衡量排序算法好坏的最重要的标志。6)排序的基本操作：比较两个关键字大小将记录从一个位置移动到另一个位置排序的时间代价主要是指执行算法中关键字的比较和记录的移动次数，因此在下面讨论的各种排序算法时，我们将给出各算法的比较次数和移动次数。1.排序的基本概念7)本章排序方法所用的存储结构：本章中，假设记录数组作为文件的存储结构，关键字为整数，文件类型说明如下:typedefstruct/*定义记录为结构类型*/{intkey;/*关键字域*/datatypeother;/*记录的其它域*/}rectype;rectypeR[n];/*R为记录类型的数组*/其中：n为文件的记录总数。本章主要内容：1.排序的基本概念2.插入排序3.选择排序4.交换排序5.归并排序第十四章排序2.插入排序插入排序（InsertionSort）将待排序的一组记录分为两个区：有序区和无序区，每次将无序区中的第一个记录按其关键字值的大小插入到有序区中的适当位置，直到无序区中的全部记录都插完为止。插入排序的分类:直接插入排序希尔排序2.插入排序－直接插入排序2.1直接插入排序1）基本思想直接插入排序是一种最简单的排序方法。具体做法是在插入第i个记录时，R1,R2,…,Ri-1已排好序，这时将Ri的关键字ki依次与关键字ki-1,ki-2，…,k1进行比较，从而找到应该插入的位置，然后将ki插入。R1,R2,…,Ri-1Ri,Ri+1,…,Rn有序区无序区注意比较的方向2)直接插入排序实例初始关键字[47]33618272112547’i=2(33)[3347]618272112547’i=3(61)[334761]8272112547’i=4(82)[33476182]72112547’i=5(72)[3347617282]112547’i=6(11)[113347617282]2547’i=7(25)[11253347617282]47’i=8(47’)[1125334747’617282]2.插入排序－直接插入排序2.插入排序－直接插入排序3）算法设计R1,R2,…,Ri-1Ri,Ri+1,…,Rn有序区无序区R0监视哨4)算法实现InsertSort(R)rectypeR[n+1];//R[0]备用，R[1]~R[n]为n个待排序记录{inti,j;for(i=2；i=n；i++)//外层循环控制进行n-1趟排序{R[0]=R[i]；//将待插入记录存放在监视哨中j=i-1；while(R[0].keyR[j].key)//在当前有序区查找插入位置{R[j+1]=R[j]；j--；//将关键字大于R[j].key的记录后移}R[j+1]=R[0]；//插入R[i]}}2.插入排序－直接插入排序为何没有j=0判断条件会不会丢失R[i]的值为何计数器从2开始5)算法说明算法采用的是查找比较操作和记录移动操作交替进行的方法。具体作法是将待插入记录R[i]的关键字依次与有序区中的关键字R[j](j=i-1,i-2,…,1)的关键字进行比较，若R[j]的关键字大于R[i]的关键字，则将R[j]后移一个位置，若R[j]的关键字小于或等于R[i]的关键字，则查找过程结束，j+1即为R[i]的插入位置。因为关键字比R[i]大的记录已经后移，故只需将R[i]插入该位置即可。2.插入排序－直接插入排序6)监视哨算法引进了一个附加记录R[0],其作用有两个:(1)进入查找循环之前，它保存了R[i]的副本，使得不致于因记录的后移而丢失R[i]中的内容；(2)在while循环中“监视”下标变量j是否越界，以避免循环内每次都要检测j是否越界。因此将R[0]称为“监视哨”，这使测试循环条件的时间大约减少一半。2.插入排序－直接插入排序7)算法分析整个排序过程只有两种运算，即比较关键字和移动记录。算法有内外两层循环，外循环表示要进行n-1趟插入排序，内循环则表示每一趟排序所需进行的关键字的比较和记录的移动。在文件正序时，关键字的比较次数和记录移动次数均取得最小值。每趟排序的关键字比较次数为1，记录移动次数为2，即：总的比较次数为Cmin=n-1,总的移动次数为Mmin=2(n-1);2.插入排序－直接插入排序当文件逆序时，关键字的比较次数和记录移动次数均取得最大值。对于要插入的第i记录，均要和前i-1个记录及“监视哨”的关键字进行比较，即每趟要进行i次比较，从移动记录的次数来讲，每趟排序中除了上面的两次移动外，还需要将关键字大于R[i]的i－1个记录后移一个位置。总的比较次数和记录的移动次数为：)(2/)1)(4()21(22maxnOnniMni)(2/)1)(2(22maxnOnniCni2.插入排序－直接插入排序由以上分析可知，当记录关键字的分布情况不同时，算法在执行过程中的时间消耗是不同的。在记录分布随机情况下，即关键字可能出现的各种排列的概率相同，则可取上面两种情况的平均值作为比较和记录移动的平均次数，约为n2/4.因此直接插入排序的时间复杂度为O(n2)空间复杂度为O(1)。直接插入排序是稳定的排序方法。2.插入排序－直接插入排序练习初始化{99}，17，23，45，60，38，47、83第1趟{17，99}，23，45，60，38，47、83第2趟{17，23，99}，45，60，38，47、83第3趟{17，23，45，99}，60，38，47、83第4趟{17，23，45，60，99}，38，47、83第5趟{17，23，38，45，60，99}，47、83第6趟{17，23，38，45，47、60，99}，83第7趟{17，23，38，45，47、60，83，99}已知待排序列为{99，17，23，45，60，38，47、83}，请写出直接插入排序的基本思路，并写出直接插入排序每一趟的排序结果。2.2希尔排序该方法是由D.L.Shell在1959年提出的，又称缩小增量排序(Diminishing-incrementsort)1）基本思想设待排序的数据对象有n个，先取一个整数d1n作为第一个增量，将文件中的全部记录分为d1个组，所有距离为d1的记录放在同一个组中，在每一个组中分别进行直接插入排序，然后取第二个增量d2d1，如取d2=d1/2，重复上述的分组和排序工作，直到最后取dl=1为止,此时，所有的记录放在同一组中进行直接插入排序。2.插入排序－希尔排序2）排序实例设待排序的数据对象有8个，增量序列取值依次为4，2，1。最后结果为：15233661727883942.插入排序－希尔排序3）希尔排序算法设计-带监视哨设某一趟希尔排序的增量为h，则整个文件被分成h组:(R1,Rh+1,R2h+1,…)，(R2,Rh+2,R2h+2,…),…,(Rh,R2h,R3h,…)因为各组记录的距离均为h，故第一组至第h组的监视哨的位置依次为1－h,2-h,…,0。如果像直接插入排序那样，将待插入记录Ri在查找插入位置之前保存到监视哨中，必须计算Ri属于哪一组，才能决定使用哪个监视哨来保存Ri。这样处理不太方便。R1-h,R2-h,R3-h,…,R0,R1,R2,R3,…,Rh，Rh+1,Rh+2,Rh+3,…R2h-1，R2h,…,Rn2.插入排序－希尔排序具体做法：R1-h,R2-h,R3-h,…,R0,R1,R2,R3,…,Rh，Rh+1,Rh+2,Rh+3,…R2h-1,…,Rna)监视哨值的设定为了避免这种计算，我们可以将Ri保存到另一个辅助记录x中，而将所有监视哨R1-h,R2-h,…,R0的关键字设置为小于文件中任何果关键字即可。b)监视哨个数的设定因为增量是变化的，所以各趟排序中所需的监视哨数目也不同，所以按照最大增量d来设置监视哨。2.插入排序－希尔排序3）希尔排序算法实现rectypeR[n+d]//R[0]~R[d-1]为d个监视哨intd[t];//d[0]~d[t-1]为增量序列SHELLSORT(rectypeR[],intd[]){inti,j,k,h;rectypetemp;//中间寄存变量intmaxint=32767;//最大整数值for(i=0;id[0];i++)R[i].key=-maxint;//所有哨兵的值置为最大负整数值k=0;//设置增量序列的开始值do{h=d[k];//取出本趟增量for(i=h+d-1;in+d;i++)//R[h+d]~R[h+d-1]插入到当前有序区{temp=R[i];//保存待插入记录j=i-h;//确定当前有序区的最后一个位置while(temp.keyR[j].key)//查找正确的插入位置{R[j+h]=R[j];//后移记录j=j-h;//得到前一记录位置}R[j+h]=temp;//插入R[j]}//本趟排序完成k++;//取下一趟排序的增量}while(h!=1);//增量为1排序后终止算法}为何从h+d-1开始为何在d[0]取值为何是i＋＋为何是j＝i－h2.插入排序－希尔排序增量为何为h4）希尔排序的特点本质上还是一种插入排序，其主要特点是：每一趟以不同的增量进行排序。希尔排序速度快的原因分析：a)大跨步踊跃式的插入排序在前面几趟希尔排序中，记录的比较是和同一组的前一个关键字进行比较，由于此时