滁州学院课程设计报告课程名称：数据结构设计题目：排序算法实现及比较系别：计算机信息工程学院专业：计算机科学与技术组别：第*组起止日期:12 年 5 月 1 日~ 12 年6月1 日指导教师:***计算机与信息工程学院二○一二年制课程设计任务书目录1.引言 (4)2.需求分析 (4)3.详细设计 (4)3.1 直接插入排序 (4)3.2折半排序 (5)3.3 希尔排序 (6)3.4简单选择排序 (6)3.5堆排序 (6)3.6归并排序 (7)3.7冒泡排序 (9)4.调试 (10)5.调试及检验 (11)5.1 直接插入排序 (11)5.2折半插入排序 (11)5.3 希尔排序 (12)5.4简单选择排序 (12)5.5堆排序 (13)5.6归并排序 (14)5.7冒泡排序 (14)6.测试与比较 (15)6.1调试步骤 (15)6.2结论 (16)7.实验心得与分析 (16)8.附录 (17)8.1直接插入排序 (17)8.2折半插入排序 (18)8.3希尔排序 (20)8.4简单选择排序 (22)8.5堆排序 (23)8.6归并排序 (26)8.7冒泡排序 (29)8.8主程序 (30)1.引言伴随着社会的发展，数据也变得越来越庞大。
如何将庞大的数据进行很好的排序，使用户更加方便的查找资料，成了一件越来越重要的问题。
对于程序员来说，这将是一个挑战。
经常查找资料的朋友都会知道，面对海量的资料，如果其查找的资料没有进行排序，那么其查找资料将会是一件非常痛苦的事情。
针对这一问题，我们自此通过一个课程设计来解决它。
理论上排序算法有很多种，不过本课程设计只涉及到七种算法。
这七种算法共包括：直接插入排序，折半插入排序，希尔排序，简单选择排序，堆排序，归并排序，冒泡排序。
本课程设计通过对这七种算法的运行情况进行对比，选择最优秀的算法来提供给用户。
希望通过我们的努力能给用户解决一些问题，带来一些方便。
2.需求分析本课程题目是排序算法的实现，由于各方面的原因，本课程设计一共要设计七种排序算法。
这七种算法共包括：直接插入排序，折半插入排序，希尔排序，简单选择排序，堆排序，归并排序，冒泡排序。
七种排序各有独到之处，因此我们要通过各种调试分析来比较其优劣长短。
为了小组分工的方便，我们特意把子函数写成Header File文件。
这样操作不仅可以使小组分工更加简洁明了，还可以方便子函数的调用，更可以使写主函数时一目了然。
为了运行时的方便，我们将七种排序方法进行编号，其中1为直接插入排序，2为折半插入排序，3为希尔排序，4为简单选择排序，5为堆排序，6为归并排序，7为冒泡排序。
通过这七种选项，可以让用户简单明了的去选择使用哪一种排序方法。
本课程就是通过对5组占用内存大小不同的数据调试来测试这七种算法运行的时间长短，从中选择面对不同大小的文件时，哪一种算法更为快捷。
软件环境本课程设计所用操作系统为Windows-XP操作系统，所使用的软件为Microsoft Visual C++ 6.0；3.详细设计3.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';3.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; //插入}3.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; //插入}}3.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;}3.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插入到该位置，元素插入实现}3.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++;}}}}3.7冒泡排序⑴算法思想：1、先将一组未排序的数组的最后一个数与倒数第二个数进行比较，并将较小的数放于两个数中较前的位置，然后将比较后的较小的数与倒数第三个进行比较，依次比较到第一个数，即可得到第一个数是所有数中最小的数；2、然后再将数组的最后一个数与倒数第二个数进行比较，并将较小的数放于两个数中较前的位置，依次比较到第二个数，3、如此循环到只剩最后两个比较，即得到排好序的一组数。