课程设计课程设计名称：排序综合专业班级： 0000000000000 学生姓名： 0000000000000学号： 00000000000000 指导教师： 00000000000000 课程设计时间： 2010.6.21-2010.6.25计算机科学与技术专业课程设计任务书说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页信息科学与工程学院课程设计成绩评价表课程名称：数据结构课程设计1、需求分析1.1、直接插入排序思路:设有一组关键字{K1,K2,…….,Kn},排序开始变认为K1是一个有序的序列,让K2插入到表长为1的有序序列,使之成为一个表长为2的有序序列, 让K3插入到表长为2的有序序列,使之成为一个表长为3的有序序列,依次类推,最后让Kn插入上述表长为n-1的有序序列,得到一个表长为n的有序序列.1.2、希尔排序思路：先取一个正整数d1(d1<n),把全部记录分成d1个组,所有距离为d1的倍数的记录看成是一组,然后在各组内进行插入排序;然后取d2(d2<d1),重复上述分组和排序操作,直到取di=1(>=1),即所有记录成为一个组为此.一般选d1约为n/2,d2为d1/2,…….,di=11.3、快速排序:（递归和非递归）思路:以第一个关键字K1为控制字，将[K1、K2、….Kn]分成两个子区，使左区的有关键字小于等于K1，右区所有关键字大于等于K1，最后控制居两个子区中间的适当位置。

在子区内数据尚处于无序状态。

将右区首、尾指针保存入栈，对左区进行与第（1）步相类似的处理，又得到它的左子区和右子区，控制字区中。

重复第（1）、（2）步，直到左区处理完毕。

然后退栈对一个个子区进行相类似的处理，直到栈空分区处理函数hoare思路：首先用两个指针i、j分别指向首、尾两个关键字，i=1，j=8。

如对(46、56、14、43、95、10、19、72)。

第一个关键字46作为控制字，该关键字所属的记录另存储在一个x变量中。

从文件右端元素r[j].key开始与控制字x.key相比较，当r[j].key大于等于x.key时，r[j]不移动，修改指针j，j--，直到r[j].key<x.key，把记录r[j]移动到文件左边i所指向的位置;然后在文件左边修改i指针,i++，让r[i].key与x.key相比较，当r[i].key小于等于x.key 时，r[i]不移动，修改指针i，i--，直到r[i].key<x.key, 把记录r[i]移动到文件右边j所指向的位置;然后在文件右边修改j指针j--。

重复上面的步骤.1.4、堆排序思路：把n个记录存于向量r之中，把它看成完全二叉树，此时关键字序列不一定满足堆的关系。

堆排序大体分为两步处理：初建堆，从堆的定义出发，当i=1、2、。

、[2/n]时应满足ki<=k2i和ki<=k2i+1.所以先取i=[n/2](它一定是第n个结点的双亲编号),将以i结点为根的子树调整为堆，然后令i=i-1，将以不结点为根的子树调整为堆。

此时可能会反复调整某些结点，直到i=1为止，堆初步建成。

堆排序，首先输出堆顶元素（一般是最小值）,让堆中最后一个元素上移到原堆顶位置，然后恢复堆。

因为经过第一步输出堆顶元素的操作后，往往破坏了堆关系，所以要恢复堆；重复执行输出堆顶元素、堆尾元素上移和恢复堆的步骤。

2、概要设计2.1、头文件#include<stdio.h>#include<stdlib.h>#include<cstdlib>#include<time.h>2.2 、ADTstruct element{int key;}list[20];struct rnode{int key;int point;};2.3、各种操作函数：（1）创建一个数组函数：int creat()；（2）输出数组函数：void print(struct element a[20],int n)；（3）保存函数：void save(struct element a[SIZE],int n, char fileName[] )（4）直接插入排序函数：void insert_sort(element a[], int n)（5）希尔排序函数：void shell(struct element a[20],int n)；（6）快速排序函数（分区处理函数）：int hoare(struct element a[20],int l,int h)；（7）非递归的快速排序函数：void quick1(struct element a[20],int n)；（8）递归的快速排序函数：void quick2(struct element a[20],int l,int h)；（9）堆排序（调整堆的函数）：void heap(struct element a[20],int i,int m)；（10）堆排序（主体函数）：void heapsort(struct element a[20],int n)；（11）时间函数：start = clock();end = clock();2.4、主函数Void main(){接受命令（选择要执行的操作）；处理命令；输出结果；}3、详细设计3.1、程序源代码：#include<stdio.h>#include<stdlib.h>#include<cstdlib>#include<time.h>#define SIZE 1000000struct element{int key;}list[SIZE];///////创建一个数组////////int creat(){int i,n;int num;n=0;printf("请输入元素个数:");scanf("%d",&num);for( i = 0;i < num; i++ ){list[n].key = rand() % 10000;n++;}return(n);}/////////////输出数组/////////////void print(struct element a[SIZE],int n){int i;for(i=0;i<n;i++)printf("%5d",a[i ].key);printf("\n");}/////////////保存到文件/////////////void save(struct element a[SIZE],int n, char fileName[] ) {int m_wr=0; // 写入TXT文件变量FILE *fp;if ( ( fp = fopen ( fileName, "w" ) ) == NULL )printf("File writer error\n");for (int m=0; m<n; m++ ){m_wr = a[m].key;fprintf ( fp, "%d ", m_wr ); // 写入TXT中}fclose ( fp );}//////////////////// 直接插入排序///////////////////void insert_sort(element a[], int n){int i, j;element next;for(i=1; i<n; i++){next = a[i];for(j=i-1;j>=0 && next.key < a[j].key;j--)a[j+1].key=a[j].key;a[j+1]=next;}printf("输出直接插入排序的结果:\n");}/////////////////希尔排序//////////////////////void shell(struct element a[SIZE],int n){int i,j,k;for(i=n;i>=1;i--)a[i].key=a[i-1].key;k=n/2;while(k>=1){for(i=k+1;i<=n;i++){a[0].key=a[i].key;j=i-k;while((a[j].key>a[0].key)&&(j>=0)){a[j+k].key=a[j].key;j=j-k;}a[j+k]=a[0];}k=k/2;}for(i=0;i<n;i++)a[i].key=a[i+1].key;printf("输出希尔排序的结果:\n");}////////////////////快速排序///////////////////////////int hoare(struct element a[SIZE],int l,int h)//分区处理函数{int i,j;struct element x;i=l;j=h;x.key=a[i].key;do{while((i<j)&&(a[j].key>=x.key))if(i<j){a[i].key=a[j].key;i++;}while((i<j)&&(a[i].key<=x.key))i++;if(i<j){a[j].key=a[i].key;j--;}}while(i<j);a[i].key=x.key;return(i);}void quick1(struct element a[SIZE],int n) //非递归的快速排序{int i,l,h,tag,top;int s[20][2];l=0;h=n-1;tag=1;top=0;do{while(l<h){i=hoare(a,l,h);s[top][0]=i+1;s[top][1]=h;h=h-1;}if(top==0)tag=0;else{l=s[top][0];h=s[top][1];top--;}}while(tag==1);}void quick2(struct element a[SIZE],int l,int h)//递归的快速排序{int i;if(l<h){i=hoare(a,l,h); //划为两个区quick2(a,l,i-1); //对左分区快速排序quick2(a,i+1,h); //对右分区快速排序}}////////////////////堆排序函数////////////////////////////调整堆的函数void heap(struct element a[SIZE],int i,int m)/*i是根结点编号,m是以i为根的子树的最后一个结点编号*/{struct element x;int j;x.key=a[i].key; //保存记录内容j=2*i; //j 为左孩子编号while(j<=m){if(j<m)if(a[j].key>a[j+1].key) //当结点i有左,右两个孩子时,j 取关键较小的孩子编号j++;if(a[j].key<x.key) //向下一层探测{a[i].key=a[j].key;i=j;j=2*i;}elsej=m+1; //x.key小于左,右孩子的关键字时,使j>m,以便结束循环}a[i].key=x.key;}//堆排序的主体函数void heapsort(struct element a[SIZE],int n)int i,v;struct element x;for(i=n;i>0;i--)a[i].key=a[i-1].key;for(i=n/2;i>=1;i--)heap(a,i,n);for(v=n;v>=2;v--){x.key=a[1].key; //堆顶堆尾元素交换a[1].key=a[v].key;a[v].key=x.key;heap(a,1,v-1); //这次比上次少处理一个记录}for(i=0;i<n;i++)a[i].key=a[i+1].key;for(i=0;i<n/2;i++){int k;k=a[i].key;a[i].key=a[n-i-1].key;a[n-i-1].key=k;}}void main()int num,l,h,c;clock_t start, end;c=1;char file1[50] = "直接插入排序.txt";char file2[50] = "希尔排序.txt";char file3[50] = "非递归的快速排序.txt";char file4[50] = "递归的快速排序.txt";char file5[50] = "堆排序.txt";printf("***********欢迎使用本系统学习各种排序*************\n");printf("*温馨提示：首先请生成用于排序的元素，以便进行排序*\n");printf("********************主菜单************************\n");printf("* 1 生成随机排序元素*\n");printf("* 2 直接插入排序*\n");printf("* 3 希尔排序*\n");printf("* 4 非递归的快速排序*\n");printf("* 5 递归的快速排序*\n");printf("* 6 堆排序*\n");printf("* 0 退出*\n");printf("**************************************************\n");while(c!=0){printf("*请输入0-6进行操作\n");scanf("%d",&c);switch(c){case 1:num=creat();print(list,num);break;case 2:start = clock();insert_sort(list,num);end = clock();print(list,num);save(list,num, file1) ;printf("The time : %d ms\n", end - start );break;case 3:start = clock();shell(list,num);end = clock();print(list,num);save(list,num,file2) ;printf("The time : %d ms\n", end - start );break;case 4:start = clock();quick1(list,num);end = clock();print(list,num);save(list,num,file3) ;printf("The time : %d ms\n", end - start );break;case 5:l=0;h=num-1;start = clock();quick2(list,l,h);end = clock();printf("输出递归快速排序结果:\n");print(list,num);save(list,num,file4);printf("The time : %d ms\n", end - start );break;case 6:start = clock();heapsort(list,num);end = clock();print(list,num);save(list,num,file5);printf("The time : %d ms\n", end - start );break;}}}//main end4、调试分析4.1、insertion_sort排序算法分析：该算法的时间复杂度为O(n*n).直接插入排序是稳定的排序方法。