排序 排序( sorting)是计算机程序设计中的一种重要操作,它 的功能是将一个数据元素(或记录)的任意序列,重 新排列成一个按关键字有序的序列 由于待排序的记录数量不同,使得排序过程中涉及的存 储器不同,可将排序方法分为两大类:一类是内部排 序,指的是待排序记录存放在计算机存储器中进行的 排序过程;另一类是外部排序,指的是待排序记录的 数量很大,以致内存一次不能容纳全部记录,在排序 过程中对外存进行访问的排序过程
排序 排序（sorting）是计算机程序设计中的一种重要操作，它 的功能是将一个数据元素（或记录）的任意序列，重 新排列成一个按关键字有序的序列。 由于待排序的记录数量不同，使得排序过程中涉及的存 储器不同，可将排序方法分为两大类：一类是内部排 序，指的是待排序记录存放在计算机存储器中进行的 排序过程；另一类是外部排序，指的是待排序记录的 数量很大，以致内存一次不能容纳全部记录，在排序 过程中对外存进行访问的排序过程
插入排序 线性插入排序的基本思想是:第1遍,将初始文 件中的记录R1看作有序子文件,将R插入这个 子文件中。若R2的关键字小于R1的关键字,则 R插在R1的前面,否则R插在R1的后面。第2 遍,将R3插入前面的两个记录的有序子文件中 得到3个记录的有序子文件。依此类推,继续 进行下去,直到将R插入到前面的n-1个记录的 有序子文件中,最后得到n个记录的有序文件
插入排序 线性插入排序的基本思想是：第1遍，将初始文 件中的记录R1看作有序子文件，将R2插入这个 子文件中。若R2的关键字小于R1的关键字，则 R2插在R1的前面，否则R2插在R1的后面。第2 遍，将R3插入前面的两个记录的有序子文件中， 得到3个记录的有序子文件。依此类推，继续 进行下去，直到将Rn插入到前面的n-1个记录的 有序子文件中，最后得到n个记录的有序文件
线性插入排序的基本思想是:第1遍,将 初始文件中的记录R1看作有序子文件, 将R2插入这个子文件中。若R2的关键 字小于R1的关键字,则R2插在R1的前 面,否则R2插在R1的后面。第2遍, 将R3插入前面的两个记录的有序子文 件中,得到3个记录的有序子文件。 依此类推,继续进行下去,直到将Rn 插入到前面的n-1个记录的有序子文 件中,最后得到n个记录的有序文件 KO K1 K2 K3 K4 K5 图9-1所示为线性插入排序的例子。 初始关键字 15 为了避免检测是否应插在R1的前面,在 R1的前面设立记录R0,它既是中间变 第一遍排序后:21(2143)89154328 量,又是监视哨。设(R1,R2,… R1)是已排序的有序子文件,则插 第二遍排序后:89(214389)154328 入R的步骤是:首先将R存放到R 然后将Ko(即原R的关键字Ki)依 第三遍排序后:15(152143 次与K,K2,…比较,若K。K -1,1-2 则R后移 第四遍排序后:43(15214343 个位置,否则停止比较和移动;最后 将R。(即原来待插入的记录R1)移到 j+1的位置上。由于R的前面有监视 第五遍排序后:28(1521284343 哨R,因此不必每次判断下标j是否 出界。算法描述如下
线性插入排序的基本思想是：第1遍，将 初始文件中的记录R1看作有序子文件， 将R2插入这个子文件中。若R2的关键 字小于R1的关键字，则R2插在R1的前 面，否则R2插在R1的后面。第2遍， 将R3插入前面的两个记录的有序子文 件中，得到3个记录的有序子文件。 依此类推，继续进行下去，直到将Rn 插入到前面的n-1个记录的有序子文 件中，最后得到n个记录的有序文件。 图9-1所示为线性插入排序的例子。 为了避免检测是否应插在R1的前面，在 R1的前面设立记录R0，它既是中间变 量，又是监视哨。设（R1，R2，…， Ri-1）是已排序的有序子文件，则插 入Ri的步骤是：首先将Ri存放到Ro中， 然后将Ko（即原Ri的关键字Ki）依 次与Ki-1，Ki-2，…比较，若Ko<Kj （j=i-1，i-2，…，1），则Rj后移一 个位置，否则停止比较和移动；最后， 将Ro（即原来待插入的记录Ri）移到 j+1的位置上。由于Ri的前面有监视 哨Ro，因此不必每次判断下标j是否 出界。算法描述如下：
void insertsort(struct node r n+lint n /*r[n1]为一维数组,其中r[为监视哨,r[1到rn为待 排序的n个记录,排序好的记录仍放在r中* i for(i=2; KrO).key) r[j+1]=rj] r[j+1]=r[0
void insertsort(struct node r[ n+1],int n) /* r[n+1]为一维数组，其中r[0]为监视哨，r[1]到r[n]为待 排序的n个记录，排序好的记录仍放在r中*/ { for(i=2;ir[0].key) { r[j+1]=r[j]; j--; } r[j+1]=r[0]; } }
折半插入排序 在线性插入排序中,我们采用顺序查找法来确定记录的插入位置。由于(R1,R2,…,R1)是有 序子文件,我们可以采用折半查找法来确定R的插入位置,这种排序称为折半插入排序。其 算法可写出如下 void binarysort(struct node rl n+l), int n) /*按关键字递增的次序对记录[1,r2]……,rm进行折半插入排序* i for(F2 K<=n: 1++) r[o}=r[; h=i-I while(k=h) {mid=(+h)2 if(r[O). key<r[mid]. key) h=mid-1 else emid+I for(上1j=l-) rl+lOri r[lr[0]; 在上面的算法中,每插入一个R,平均比较次数为log2io
折半插入排序 在线性插入排序中，我们采用顺序查找法来确定记录的插入位置。由于（R1，R2，…，Ri-1）是有 序子文件，我们可以采用折半查找法来确定R1的插入位置，这种排序称为折半插入排序。其 算法可写出如下： void binarysort(struct node r[ n+1],int n) /*按关键字递增的次序对记录r[1],r[2],……,r[n]进行折半插入排序*/ { for(i=2;i=l;j--) r[j+1]=r[j]; r[l]=r[0]; } } 在上面的算法中，每插入一个R1，平均比较次数为log2 i
希尔排序 希尔排序( Shells method)又称“缩小增量排序”( Diminishing Increment sort), 是由 D.L. Shell在1959年提出来的。它的作法是:先取定一个小于n的整数d1作为第 个增量,把文件的全部记录分成d1个组,所有距离为d1的倍数的记录放在同 个组中,在各组内进行直接插入排序;然后,到第二个增量d2<d1重复上述分组和 排序,直至所取的增量d=1(d<d-1<.<d2<d1),即所有记录放在同一组中进行 直接插入排序为止 先从一个具体的例子来看希尔排序。假设待排序文件有10个记录,其关键字分别是 49,38,65,97,76,13,27,49,55,04。增量序列取值依次为:5,3,1 第一趟排序时,d1=5,整个文件被分成5组:(R1,R),(R2,R7),…,(Rs, R10)各组中的第1个记录都自成一个有序区,我们依次将各组的第2个记录R6, R,R10分别插入到各组的有序区中,使文件的各组均是有序的,其结果见图9- 2的第七 第二趟排序时,d2=3,整个文件分成三组:(R1,R4,R,R10),(R2,R3,Rs (R3,R6,R),各组的第1个记录仍自成一个有序区,然后依次将各组的第2个 记录R4,R,R6分别插入到该组的当前有序区中,使得(R1,R4),(R2,R5), (R3,R6)均变为新的有序区,接着依次将各组的第3个记录R7,R8,R9分别插 入到该组当前的有序区中,又使得(R1,R4,R (R,R5,R),(R3,R R)均变为新的有序区,最后将R10插入到有序区(R1,R4,R)中就得到第 趟排序结果。 最后一趟排序时,d3=1,即是对整个文件做直接插入排序,其结果即为有序文件
希尔排序 希尔排序（Shell’s Method）又称“缩小增量排序”（Diminishing Increment Sort）， 是由D.L.Shell在1959年提出来的。它的作法是：先取定一个小于n的整数d1作为第 一个增量，把文件的全部记录分成d1个组，所有距离为d1的倍数的记录放在同一 个组中，在各组内进行直接插入排序；然后，到第二个增量d2<d1重复上述分组和 排序，直至所取的增量dt=1（dt<dt -1<…<d2<d1），即所有记录放在同一组中进行 直接插入排序为止。 先从一个具体的例子来看希尔排序。假设待排序文件有10个记录，其关键字分别是： 49，38，65，97，76，13，27，49/，55，04。增量序列取值依次为：5，3，1。 第一趟排序时，d1=5，整个文件被分成5组：（R1，R6），（R2，R7），…，（R5， R10）各组中的第1个记录都自成一个有序区，我们依次将各组的第2个记录R6， R7，…R10分别插入到各组的有序区中，使文件的各组均是有序的，其结果见图9- 2的第七行。 第二趟排序时，d2=3，整个文件分成三组：（R1，R4，R7，R10），（R2，R5，R8）， （R3，R6，R9），各组的第1个记录仍自成一个有序区，然后依次将各组的第2个 记录R4，R5，R6分别插入到该组的当前有序区中，使得（R1，R4），（R2，R5）， （R3，R6）均变为新的有序区，接着依次将各组的第3个记录R7，R8，R9分别插 入到该组当前的有序区中，又使得（R1，R4，R7），（R2，R5，R8），（R3，R6， R9）均变为新的有序区，最后将R10插入到有序区（R1，R4，R7）中就得到第二 趟排序结果。 最后一趟排序时，d3=1，即是对整个文件做直接插入排序，其结果即为有序文件
若不设置监视哨,根据上例的分析不难写出希尔排序算 法,请读者自行完成之。下面我们先分析如何设置监 视哨,然后给出具体算法。设某一趟希尔排序的增量 为h,则整个文件被分成h组:(R1,RH1,R2h+1,…), (R2,R1+2,R2h+2, (Rh, RL, R 因为各组中记录之间的距离均为是h,故第1组至第h组 的哨兵位置依次为1-h,2-h,…,0。如果象直接插入 排序算法那样,将待插入记录R:(h1≤iN)在查找插 入位置之前保存到监视哨中,那么必须先计Ri属于哪 组,才能决定使用哪个监视哨来保存Ri。为了避免 这种计算,我们可以将Ri保存到另一个辅肋记录X中, 而将所有监视哨R1,R2h,…,R0的关键字,设置为 小于文件中的任何关键字即可。因为增量是变化的, 所以,各趟排序中所需的监视哨数目也不相同,但是 我们可以按最大增量d1来设置监视哨
若不设置监视哨，根据上例的分析不难写出希尔排序算 法，请读者自行完成之。下面我们先分析如何设置监 视哨，然后给出具体算法。设某一趟希尔排序的增量 为h，则整个文件被分成h组：（R1，Rh+1，R2h+1，…）， （R2，Rh+2，R2h+2，…），…（Rh，R2h，R3h，…）， 因为各组中记录之间的距离均为是h，故第1组至第h组 的哨兵位置依次为1-h，2-h，…，0。如果象直接插入 排序算法那样，将待插入记录Ri（h+1≤i≤N） 在查找插 入位置之前保存到监视哨中，那么必须先计Ri属于哪 一组，才能决定使用哪个监视哨来保存Ri。为了避免 这种计算，我们可以将Ri保存到另一个辅肋记录X中， 而将所有监视哨R1-h，R2-h，…，R0的关键字，设置为 小于文件中的任何关键字即可。因为增量是变化的， 所以，各趟排序中所需的监视哨数目也不相同，但是 我们可以按最大增量d1来设置监视哨
rectype r[n+d /*Rd1-]为d1个监视哨 int dt /*dO到dt]为增量序列* SHELLSORT(R, d) Rectype r: int d[: fint i,j,k,h ectype temp int maxint=32767 /*机器中最大整数* for(F0; K<d[0]: 1++) RI.key=-maxint /*设置哨兵* K=0: H=d[k]: *取本趟增量* For(Fh+di: K<n+dl: i++) /*Rhd到Rn+dl-1插入当前有序区* /保存待插入记录R[]*/ whie(temp.key<Rkey)/*查找正确的插入位置* R[+h]R[i]} 后移记录* J *得到前一记录位置* RIh=temp; /插入R[*/ /*本趟排序完成* k++; i while (h! =1) /*增量为1排序后终止算法* /*SHELLSORT*/
rectype R[n+d1]； /* R[d1 -1]为d1个监视哨*/ int d[t]； /* d[0]到d[t-1]为增量序列*/ SHELLSORT(R,d) Rectype R[ ]； int d[ ]； {int i，j，k，h； rectype temp; int maxint=32767； /*机器中最大整数*/ for (i=0；i<d[0]；i++) R[i].key=-maxint； /*设置哨兵*/ K=0； Do{ H=d[k]； /*取本趟增量*/ For(i=h+di；i<n+d1；i++) /*R[h+d1]到R[n+d1-1]插入当前有序区*/ {temp=R[i]}； /*保存待插入记录R[i]*/ j=i-h； while(temp.key<R[j].key) /*查找正确的插入位置*/ {R[j+h]=R[j]}； /*后移记录*/ j=j-h； /*得到前一记录位置*/ } R[j+h]=temp； /*插入R[i]*/ } /*本趟排序完成*/ k++； } while (h！=1)； /*增量为1排序后终止算法*/ } /*SHELLSORT*/
读者可能看出,当增量h=1时, SHELLSORT算法与 INSERTSORT基 本一致 对希尔排序的分析提出了许多困难的数学问题,特别是如何选择增 量序列才能产生最好的排序效果,至今没有得到解决。希尔本为 最初提出取d1=n/2,d1=-d21,d,=1,t=山og2。后来又 有人提出其它选择增量序列的方法,如d+1=(dl)/3,d=1, t=og3n1;以及d1=-d1)2-,d=1,t=山og2n-1。 为什么希尔排序的时间性能优于直接插入排序呢?我们知道直接插 入排序在文件初态为正序时所需要时间最少,实际上,当文件初 基本有序时直接插入排序所需的比较和移动次数均较少。另一面, 当n值较小时,n和n2的差别也较小,即直接插入排序的最好时间 复杂度On)和最坏时间复杂度On2)差别不大。在希尔排序时增量 较大,分组较多,每组的记录数目少,故各组内直接插入较快 后来增量d逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐 增多,但由于已经按d1作为距离排过序,使文件较近于有序状态, 所以新的国趟排序过程也较快。因此,希尔排序在较率上较直接 接入排序有较大的改进 希尔排序是不稳定的。参见图9-2的例子,该例中两个相同关键字49 在排序前后的相对次序发生了变化
读者可能看出，当增量h=1时，SHELLSORT算法与INSERTSORT基 本一致。 对希尔排序的分析提出了许多困难的数学问题，特别是如何选择增 量序列才能产生最好的排序效果，至今没有得到解决。希尔本为 最初提出取d1=┗n/2┛ ，di+1=┗di/2 ┛ ，dt=1，t=┗log2 n┛。后来又 有人提出其它选择增量序列的方法，如di+1=┗(di-1)/3┛，dt=1， t=┗log3n-1┛；以及di+1=┗(di-1 )/2┛ ，dt=1，t=┗log2 n -1┛。 为什么希尔排序的时间性能优于直接插入排序呢？我们知道直接插 入排序在文件初态为正序时所需要时间最少，实际上，当文件初 基本有序时直接插入排序所需的比较和移动次数均较少。另一面， 当n值较小时，n和n 2的差别也较小，即直接插入排序的最好时间 复杂度O(n)和最坏时间复杂度O(n2 )差别不大。在希尔排序时增量 较大，分组较多，每组的记录数目少，故各组内直接插入较快， 后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐 增多，但由于已经按di-1作为距离排过序，使文件较近于有序状态， 所以新的国趟排序过程也较快。因此，希尔排序在较率上较直接 接入排序有较大的改进。 希尔排序是不稳定的。参见图9-2的例子，该例中两个相同关键字49 在排序前后的相对次序发生了变化
选择排序 选择排序( selection sort)也是一种简单排序法。一个记录最多只需进行 次交换就可以直接到达它的排序位置。 设待排序的文件为(R1,R2,…,Rn),进行选择排序的基本步骤如下: (1)置i为1 (2)当in时,重复下列步骤; 1)当(Ri,…,Rn)中选出一个关键字最小的记录Rmin,若Rmin不是R,即 Amini则交换Ri和Rmin的位置;否则,不进行交换。 2)i的值加1。 第1遍扫描时,在n个记录中为了选出最小关键字的记录,需要进行n-1次比 较,第2扫描时,在余下的n-1记录中,再选出具有最小关键字的记录需 要比较n-2次,…第n-1扫描时,在最后的2个记录中,比较1次选出最小 关键字的记录
选择排序 选择排序（selection sort）也是一种简单排序法。一个记录最多只需进行一 次交换就可以直接到达它的排序位置。 设待排序的文件为（R1，R2，…，Rn），进行选择排序的基本步骤如下： （1）置i 为1； （2）当i<n时，重复下列步骤； 1）当(Ri，…，Rn)中选出一个关键字最小的记录Rmin，若Rmin不是Ri，即 Rmin≠i则交换Ri和Rmin的位置；否则，不进行交换。 2）i的值加1。 第1遍扫描时，在n个记录中为了选出最小关键字的记录，需要进行n-1次比 较，第2扫描时，在余下的n-1记录中，再选出具有最小关键字的记录需 要比较n-2次，……第n-1扫描时，在最后的2个记录中，比较1次选出最小 关键字的记录