会计学假设含有n个记录的序列为｛R1,R2,…,Rn｝,其相应的关键字序列为｛K1,K2,…,Kn｝,所谓排序就是将记录按关键字非递减(或非递增)的顺序重新排列起来。在待排序的记录中若有多个相同的关键字,在用某种方法排序之后,这些关键字相同的记录相对先后次序不变,则称这种排序方法是稳定的;否则是不稳定的。本章所介绍的内部排序方法包括插入排序、交换排序、选择排序、归并排序和基数排序。前四类排序是通过比较关键字的大小(dàxiǎo)决定记录先后次序,也称为比较排序。基数排序是不经关键字比较的排序方法。为了讨论方便,在此把排序关键字假设为整型。记录的结构定义为:structnode｛intkey;/*排序(páixù)关键字域*/intoth;/*其它域,根据需要自己设定*/｝9.2插入排序/例9.1设有一组关键字序列｛55,22,44,11,33｝,这里n=5,即有5个记录。如图9.1所示。请将其按由小到大的顺序排序在具体实现Ki向前边插入时,有两种方法。一种方法是让Ki与K1,K2,…顺序比较;另一种方法是Ki与Ki-1,Ki-2…倒着比较。这里选用后一种方法。用一维数组r做存储(cúnchǔ)结构,n表示记录个数,MAXSIZE为常量，且MAXSIZE>n。则算法如下:算法9.1voidstinsort(structnoder［MAXSIZE］,intn)｛for(i=2;i<=n;i++)/*共进行n-1趟插入*/｛r［0］=r［i］;/*r［0］为监视哨,也可做下边循环结束标志*/j=i-1;while(r［j］.key>r［0］.key)｛r［j+1］=r［j］;j--;｝r［j+1］=r［0］;/*将r［0］即原r［i］记录内容,插到r［j］后一位置*/｝｝/*stinsort*/此算法(suànfǎ)外循环n-1次,在一般情况下内循环平均比较次数的数量级为Ｏ(n),所以算法(suànfǎ)总时间复杂度为Ｏ(n2)。由于比较过程中,当Kj与K0相等时并不移动记录,因此直接插入排序方法是稳定的。直接插入排序也可用单链表做存储结构。当某结点i的关键字Kj与前边有序表比较时,显然先与K1比较,再与K2比较,……,即从链表表头结点开始向后逐一比较更合适。另外,直接(zhíjiē)插入排序在原关键字序列基本有序或n值较小时,它是一种最常用的排序方法,它的时间复杂度接近于O(n)。但是,当n值又较大时,此方法就不再适用。9.2.2折半插入排序当直接插入排序进行到某一趟时,对于r［i］.key来讲,前面i-1个记录已经按关键字有序。此时不用直接插入排序的方法,而改为折半查找(cházhǎo),找出r［i］.key应插的位置,然后插入。这种方法就是折半插入排序（binaryinsertionsort）。算法如下:算法9.2voidbinasort(structnoder［MAXSIZE］,intn)｛for(i=2;i<=n;i++)｛〖ZK(〗r［0］=r［i］;l=1;h=i-1;while(l<=h)｛mid=(l+h)/2;if(r［0］.key<r［mid］.key)h=mid-1;elsel=mid+1;｝for(j=i-1;j>=l;j--)r［j+1］=r［j］;r［l］=r［0］;｝｝/*binasort*/9.2.3希尔排序希尔排序（shellsort）是D．Ｌ．希尔（D.L.Shell）提出的“缩小增量”的排序方法。它的作法不是每次一个元素挨一个元素的比较,而是初期选用大跨步（增量较大）间隔比较,使记录跳跃式接近它的排序位置;然后增量缩小;最后增量为1,这样记录移动次数大大减少,提高了排序效率。希尔排序对增量序列的选择没有严格规定。算法思路:先取一个正整数d1(d1<n),把全部记录分成d1个组,所有距离为d1的倍数的记录看成(kànchénɡ)一组,然后在各组内进行插入排序;然后取d2(d2<d1),重复上述分组和排序操作，直到取d1=1(i>=1),即所有记录成为一个组为止。一般选d1约为n/2,d1为d1/2,d3为d1/2,…,d1=1。例9．2有一组关键字｛76,81,60,22,98,33,12,79｝,将其按由小到大的顺序排序。这里n=8,取d1=4,d2=2,d3=1,其排序过程如图9.2所示。算法实现(shíxiàn)见算法9.3。算法9.3voidshellsort(structnoder［MAXSIZE］,intn)｛k=n/2;/*k值代表前文中的d值*/while(k>=1)｛for(i=k+1;i<=n;i++)