目录1.引言............................................................................................................................ 错误！未定义书签。

2.需求分析 (2)3.详细设计 (2)3.1 直接插入排序 (2)3.2折半排序 (2)3.3 希尔排序 (4)3.4简单选择排序 (4)3.5堆排序 (4)3.6归并排序 (5)3.7冒泡排序 (7)4.调试 (8)5.调试及检验 (9)5.1 直接插入排序 (9)5.2折半插入排序 (9)5.3 希尔排序 (10)5.4简单选择排序 (10)5.5堆排序 (11)5.6归并排序 (12)5.7冒泡排序 (12)6.测试与比较................................................................................................................ 错误！未定义书签。

6.1调试步骤......................................................................................................... 错误！未定义书签。

6.2结论 (13)7.实验心得与分析 (13)8.附录 (15)8.1直接插入排序 (15)8.2折半插入排序 (16)8.3希尔排序 (18)8.4简单选择排序 (20)8.5堆排序 (21)8.6归并排序 (24)8.7冒泡排序 (27)8.8主程序 (28)1.需求分析课程题目是排序算法的实现，课程设计一共要设计八种排序算法。

这八种算法共包括：堆排序，归并排序，希尔排序，冒泡排序，快速排序，基数排序，折半插入排序，直接插入排序。

为了运行时的方便，将八种排序方法进行编号，其中1为堆排序，2为归并排序，3为希尔排序，4为冒泡排序，5为快速排序，6为基数排序，7为折半插入排序8为直接插入排序。

软件环境：Windows-7操作系统，所使用的软件为c-Free；2.概要设计2.1 直接插入排序⑴算法思想：直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到一个已排好序的有序表中，从而得到一个新的、记录数增一的有序表。

在自i-1起往前搜索的过程中，可以同时后移记录。

整个排序过程为进行n-1趟插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。

⑵程序实现及核心代码的注释：for (i = 1 ; i < r.length ;++i )for(j=0;j < i;++j)if(r.base[i] < r.base[j]){temp = r.base[i]; //保存待插入记录for(i= i ;i > j; --i )r.base[i] = r.base[i-1]; //记录后移r.base[j] = temp; //插入到正确的为位置}r.base[r.length] ='\0';2.2折半排序⑴算法思想：由于折半插入排序的基本操作是在一个有序表中进行查找和插入，这个“查找”操作可利用折半查找来实现，由此进行的插入排序称之为折半插入排序。

折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，这般插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。

因此，这般插入排序的时间复杂度仍为O（n2）。

⑵程序实现及核心代码的注释：void zb(FILE *fp){ //对顺序表作折半插入排序for ( i = 1 ; i < r.length ; i++ ){temp=r.base[i]; //将r.base[i]寄存在temp中low=0;high=i-1;while( low <= high ) //在base[low]到key[high]中折半查找有序插入的位置{m = (low+high)/2; //折半if ( temp < r.base[m] )high = m-1; //插入低半区elselow = m+1; //插入高半区}for( j=i-1; j>=high+1; --j )r.base[j+1]= r.base[j]; //记录后移r.base[high+1]=temp; //插入}2.3 希尔排序⑴算法思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

其中，子序列的构成不是简单的“逐段分割”，而是将分隔某个“增量”的记录组成一个子序列。

⑵程序实现及核心代码的注释：for(k = 0; k < 10 ; k++){m = 10 - k;for( i = m ; i < r.length; i ++ )if(r.base[i] < r.base[i - m]){temp = r.base[i]; //保存待插记录for(j = i - m ; j >= 0 && temp < r.base[j]; j -= m)r.base[ j + m ] = r.base[j]; //记录后移，查找插入位置r.base[ j + m ] = temp; //插入}}2.4简单选择排序⑴算法思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

⑵程序实现及核心代码的注释：for ( i = 0 ; i < r.length ; i++ ){ //i为排好序的数的下标，依次往后存放排//好序的数temp=r.base[i]; //将待放入排好序的数的下标的数保存for( j = i,m = j +1 ; m < r.length ; m++) //找出未排序的数中最小的数的循环；if(r.base[j] > r.base[m])j = m;r.base[i] = r.base[j]; //把下标为j的数与i数互换；r.base[j] = temp;}2.5堆排序⑴算法思想：堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。

将序列所存储的元素A[N]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)结点的元素。

算法的平均时间复杂度为O(N log N)。

⑵程序实现及核心代码的注释：void dp(FILE *fp){for(i = r.length / 2;i >= 1 ; --i) //把r.base[1...r.length]建成大顶堆HeapAdjust(r.base,i,r.length);for(i = r.length ;i >= 2 ; --i){temp = r.base[1];r.base[1] = r.base[i];r.base[i] = temp;HeapAdjust(r.base,1,i-1); //将r.base[1...i-1]重新调整为大顶堆}void HeapAdjust(char *r,int k,int m){i=k; x=r[i]; j=2*i; //沿key 较大的孩子节点向下筛选while(j<=m) //j为key较大的记录的下标{if( (j<m) && (r[j]>r[j+1]) )j++;if(x>r[j]){ //插入字符比当前的大，交换r[i] =r[j];i = j;j *= 2;}else //否则比较停止。

j = m + 1;}r[i] = x; //把字符x插入到该位置，元素插入实现}2.6归并排序⑴算法思想：先将相邻的个数为1的每两组数据进行排序合并；然后对上次归并所得到的大小为2的组进行相邻归并；如此反复，直到最后并成一组，即排好序的一组数据。

⑵程序实现及核心代码的注释：void merge(SqList6 r,int h ,int m ,int w ,SqList6 t){ //对相邻两组数据进行组合排序；int i,j,k;i = h ;j = m + 1; //j为合并的第二组元素的第一个数位置k =h-1；// k为存入t中的数的位置；while((i <= m)&&(j <= w)){ //依次排列两组数据k++;if(r.base[i] <= r.base[j]) //将第一组数据与第二组数据分别比较；t.base[k] = r.base[i++];elset.base[k] = r.base[j++];}if(i > m) //第一组数据先排完的情况while(j <= w) t.base[++k]=r.base[j++];elsewhile(i <= m) t.base[++k]=r.base[i++];}void tgb(int s,int n,SqList6 r,SqList6 t){ //对数据进行每组s个数的归并排序；int i=1; //i为要合并两组元素的第一个数位置；while(i<=(n-2*s+1)){merge(r,i,i+s-1,i+2*s-1,t); //i+s-1为要合并的第一组元素的最后一//数位置、i+2*s-1 为要合并的两组元素//最后一个数位置；i=i+2*s;}if(i<(n-s+1)) //考虑n不能被s整除，如果余下的数少于//2*s 但大于s，也就是余下的数不能凑成//两组，凑一组有余,则把余下的数进行组//合，并对其进行排序；merge(r,i,i+s-1,n,t);else //如果余下的数少于s，则余下的数进行组//合，并进行排序；while(i<=n)t.base[i]=r.base[i++];}void gb(FILE *fp) // 归并主函数；{n = r.length;SqList6 t;t.base=(char *) malloc(r.stacksize*sizeof(char));//给待排序的数组t申请内存；while(s<n) //每组元素不断增加循环进行合并排序；{tgb(s,n,r,t); // s为每组元素的个数、n为元素总个数、r//为原数组，t为待排序的数组，进行归并排s*=2; //序；把元素个数相同的两组合并并进行重新//定义成新的一组，此组元素个数为2*s；if(s<n){ tgb(s,n,t,r); s *= 2; }//当元素个数小于n时，对其进行合并排序；else //当元素个数大于n时，对剩下的数排序；{i=0;while(i<=n){r.base[i]=t.base[i+1];i++;}}}}2.7冒泡排序⑴算法思想：1、先将一组未排序的数组的最后一个数与倒数第二个数进行比较，并将较小的数放于两个数中较前的位置，然后将比较后的较小的数与倒数第三个进行比较，依次比较到第一个数，即可得到第一个数是所有数中最小的数；2、然后再将数组的最后一个数与倒数第二个数进行比较，并将较小的数放于两个数中较前的位置，依次比较到第二个数，3、如此循环到只剩最后两个比较，即得到排好序的一组数。