数据结构专业课程设计样本.doc

课 程 设 计 说 明 书

课程名称： 数据结构和算法
设计题目： 多个排序
院 系： 计算机科学和信息工程学院
学生姓名：
学 号：
专业班级： 计科嵌入式（12-1）
指导老师：

年 月 日
课 程 设 计 任 务 书
设计题目
表示式计算程序设计
学生姓名

所在院系
计科
专业、年级、班
12计科（嵌入式）
设计要求：

1) 采取以下七种方法实现上述问题求解：插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序。
2) 统计每一个排序方法性能（以上机运行程序所花费时间为准进行对比），找出其中两种较快方法。并将数据序列和不一样查找算法性能结果统计入txt文件。

学生应完成工作：
1. 利用随机函数产生N个随机整数（10000以上）。
2. 对这些数字进行排序。
3. 采取插入、希尔、起泡、快速、选择、归并、堆排序方法处理问题。
4. 对不一样排序算法进行性能比较并统计。

参考文件阅读：
1. 《数据结构(C语言版)》 严蔚敏 清华大学出版社
2. 《C语言程序设计》 丁峻岭 中国铁道出版社
3. 《C程序设计》 谭浩强 清华大学出版社

工作计划：

任务下达日期： 年 月 日
任务完成日期： 年 月 日

指导老师（署名）： 学生（署名）：

多个排序

摘 要：

排序是算法中最基础问题之一，经典排序算法是前人不停总结得到，基于比较方法是比较直观方法，关键存在插入法排序、堆排序、希尔排序、归并排序、快速排序，每一个排序算法全部有自己优缺点，比如插入法排序适适用于那些长度短排序，要是长话，有些爱莫能助啦，堆排序关键是依据了二叉堆特征，不过创建堆过程也是一个复杂问题，希尔排序过程是一个不停正确过程，不过现在也只是一个经验方法。归并排序是一个递归问题，采取分治思想实现，不过这种算法需要额外存放空间，快速排序即使是实践中比较常见算法，不过对于有序数组采取快速排序就是灾难。比较型算法时间复杂度最优也只能抵达O(NlogN)。

关键词：

归并排序 快排排序 选择排序 冒泡排序
插入排序 堆排序 希尔排序 内部排序

目 录

1. 设计背景 4
1.1问题描述 4
1.2 问题分析 4
2.设计方案 4
2.1 算法设计 4
2.2 功效模块分析 6
3.关键算法步骤图 15
4. 结果和结论 16
4.1正确结果 16
4.2错误信息 18
5. 算法复杂度和稳定性分析 18
6. 收获和致谢 19
7. 参考文件 19
8. 附件 20

1. 设计背景

1.1问题描述

利用随机函数产生N个随机整数（10000以上），对这些数进行多个方法进行排序。包含：插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序。

1.2 问题分析

经典排序算法是前人不停总结得到，基于比较方法是比较直观方法，关键存在插入法排序、堆排序、希尔排序、归并排序、快速排序，每一个排序算法全部有自己优缺点。

2. 设计方案

2.1 算法设计

（1） 选择排序

在待排序一组数据元素中，选出最小一个数据元素和第一个位置数据元素交换；然后在剩下数据元素当中再找最小和第二个位置数据元素交换，循环到只剩下最终一个数据元素为止。

（2） 冒泡排序
相邻两个元素进行比较，将小调到前面，大调到后面。

（3） 插入排序
待排序统计放在数组R[0„n-1]中排序过程中某一时刻，R被划分成两个子区间R[0,i-1] (有序和)R[i„n-1](无序)。直接插入基础操作是将目前无序区一个统计R[i]插入到有序区R[0„i-1]中合适位置

（4） 快速排序
在待排序数组n个元素中取一个元素(通常取第一个)，将其移动到这么位置：在其之前元素值全部小于它，在其以后元素全部大于它，这么是一趟快速排序；然后对数组两个部分进行一样操作，直到每部分只有一个统计为止；总而言之，每趟使表第一个元素放在合适位置，将表两分，再对两子表进行一样递归划分，直至划分子表长度为1。

（5）堆排序
堆排序中 heap 算法时间复杂度和堆所对应完全二叉树树高度 log2n 相关。而 heapsort 中对 heap 调用数量级为n，所以堆排序整个时间复杂度为O(nlog2n) 。而且堆排序是不稳定。堆排序利用了大根堆(或小根堆)堆顶统计关键字最大(或最小)这一特征，使得在目前无序区中选择最大(或最小)关键字统计变得简单。

（6）归并排序
将两个或两个以上有序表组成一个新有序表。

（7） 希尔排序
将无序数组分割为若干个子序列，子序列不是逐段分割，而是相隔特定增量子序列，对各个子序列进行插入排序；然后再选择一个更小增量，再将数组分割为多个子序列进行排序......最终选择增量为1，即使用直接插入排序，使最终数组成为有序。增量选择：在每趟排序过程全部有一个增量，最少满足一个规则 增量关系 d[1] > d[2] > d[3] >..> d[t] = 1 (t趟排序)；依据增量序列选择其时间复杂度也会有改变，这个不少论文进行了研究，在此处就不再深究；本文采取首选增量为n/2,以此递推，每次增量为原先1/2，直到增量为1。

2.2 功效模块分析

1. 数据输入：采取随机函数实现输入数据表。
int input_num()
{
printf("您要给多少个数排序？\n\t\t");
scanf("%d",&data_num);
srand(NULL);
printf("随机产生%d个数:\n\t\t",data_num);
for(int i=1;i<=data_num;i++)
{
data_array[i]=rand()%10000000;
printf("%d\n",data_array[i]);
old[i]=data_array[i];
printf("\n\t\t");
}
}

2. 数据输出：for循环输出即可。
int outnew0()
{
printf("排序后结果为:");
for(int i=data_num;i>=1;i--)
printf("%d%s",data_array[i],i!=1?" ":"\n");
}
其中增加了输出空格和换行区分。

3. 主界面实现：
printf("DATE:May twenty \n");
printf("All Copyright Reserved @- Wang Guangchun \n");
printf("ADDRESS: 604 AYIT\r\n\n\n");
printf("——————————————————— \n");
printf("——————多种排序比较————————— \n");
printf("默认从大到小输出，能够选择9进行切换\n");
printf("——————————————————— \n");
printf(" * * \n");
printf(" * * * \n");
printf(" * * \n");
printf(" * 520 * \n");
printf(" * 欢迎 * \n");
printf(" * 使用 * \n");
printf(" * * \n");
printf(" * \n");

printf("欢迎再次使用!!!\n\r\n");
printf("*******************************************\n");
printf("** . ..... . . ..... **\n");
printf("** . . . . . . **\n");
printf("** . . . . . ..... **\n");
printf("** . . . . . . **\n");
printf("** ..... ..... . ..... **\n");
printf("*******************************************\n");

4. 人机交互界面：
printf("\n——————————————————— \n");
printf("——————请输入指令———————— \n");
printf("————********************————— \n");
printf("————$ 1.快速排序 $————— \n");
printf("————$ 2.归并排序 $————— \n");
printf("————$ 3.堆排序 $————— \n");
printf("————$ 4.希尔排序 $————— \n");
printf("————$ 5.插入排序 $————— \n");
printf("————$ 6.选择排序 $————— \n");
printf("————$ 7.冒泡排序 $————— \n");
printf("————$ 8.重新随机输入 $————— \n");
printf("————$ 9.选择排序方法 $————— \n");
printf("————********************————— \n");
printf("————— 0.退出 —————— \n");
printf("——————————————————— \n");
printf("请选择：\n");

printf("——————请输入指令———————— \n");
printf("————********************————— \n");
printf("————$ 1.从小到大 $————— \n");
printf("————$ 0.从大到小 $————— \n");
printf("————********************————— \n");
printf("————— 87.退出 —————— \n");
printf("——————————————————— \n");
printf("请选择：\n");

5. 排序方法实现：
（1）选择排序
void chose_sort(int a[],int n)
{
int min,temp;
for(int i=0;i<n;i++)
{
min=i;
for(int j=i;j<n;j++)
if(a[min]>a[j])
min=j;
temp=a[min];
a[min]=a[i];
a[i]=temp;
}
}

（2） 希尔排序
void ShellInsert(int *a,int d,int n)
{
for (int i=d;i<n;i++)//从第2个数据开始插入
{
int j=i-d;
int temp=a[i];//统计要插入数据
while(j >= 0&&a[j]>temp)//从后向前，找到比其小数位置
{
a[j+d]=a[j];//向后挪动
j-=d;
}
if(j!=i-d)//存在比其小数
a[j+d]=temp;
}
}
void ShellSort(int* a,int n)
{
int d=n/2;//初始增量设为数组长度二分之一
while(d>=1)
{
ShellInsert(a,d,n);
d=d/2;//每次增量变为上次二分之一
}
}

（3） 归并排序：
void __merge(int a[],int first,int mid,int last,int temp[])
{
int i=first,j=mid+1,m=mid,n=last,k=0;
while(i<=m&&j<=n)
{
if(a[i]<=a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}
while(i<=m)
temp[k++]=a[i++];
while(j<=n)
temp[k++]=a[j++];
for(i=0;i<k;i++)
a[first+i]=temp[i];
}
void MergeSort(int a[],int first,int last,int temp[])
{
if(first<last)
{
int mid=(first+last)/2;
MergeSort(a,first,mid,temp);
MergeSort(a,mid+1,last,temp);
__merge(a,first,mid,last,temp);
}
}
bool MergeSort(int a[],int n)
{
int *p=new int[n];
if(p==NULL)
return false;
else
{
MergeSort(a,0,n-1,p);
delete[] p;
return true;
}
}
（4） 堆排序：
void HeapAdjust(int *a,int i,int size)//调整堆
{
int lchild=2*i;//i左孩子节点序号
int rchild=2*i+1;//i右孩子节点序号
int max=i;//临时变量
if(i<=size/2)//假如i是叶节点就不用进行调整
{
if(lchild<=size&&a[lchild]>a[max])
max=lchild;
if(rchild<=size&&a[rchild]>a[max])
max=rchild;
if(max!=i)
{
swap(a[i],a[max]);
HeapAdjust(a,max,size);//避免调整以后以max为父节点子树不是堆
}
}
}
void BuildHeap(int *a,int size)//建立堆
{
int i;
for(i=size/2;i>=1;i--)//非叶节点最大序号值为size/2
HeapAdjust(a,i,size);
}
void HeapSort(int *a,int size)//堆排序
{
int j=1;
BuildHeap(a,size);
for(int i=size;i>=1;i--)
{
swap(a[1],a[i]); //交换堆顶和最终一个元素，即每次将剩下元素中最大者放到最终面
//BuildHeap(a,i-1); //将余下元素重新建立为大顶堆
HeapAdjust(a,1,i-1); //重新调整堆顶节点成为大顶堆
}
}

（5） 冒泡排序：
void maopao()
{
int temp;
for(int i=1;i<=data_num;i++)
for(int j=i+1;j<=data_num;j++)
if(data_array[i]>data_array[j])
{
temp=data_array[i];
data_array[i]=data_array[j];
data_array[j]=temp;
}
}

（6） 插入排序：
void charu()
{
int i,j;
int temp;
printf("插入排序:\n");
for(i=1;i<=data_num;i++)
{
int temp=data_array[i];
for (j=i;j>0 && temp<data_array[j-1];j--)
{
data_array[j]=data_array[j-1];
}
data_array[j]=temp;
}
if(!t)
outnew0();
else
outnew1();
}

（7） 快速排序：
void kuaisu1()//快速排序1
{
printf("快速排序:\n");
sort(data_array+1,data_array+data_num+1);
if(!t)
outnew0();
else
outnew1();
}

3.关键算法步骤图 主程序

产生1组随机数

将随机数保留在数组中

希尔排序
堆排序
冒泡排序
选择排序
插入排序
归并排序
快速排序

选择排序方法

输出无序数组排序后结果

选择操作方法

4. 结果和结论
4.1 正确结果
1. 主界面 人机交互

2. 输入界面

3. 选择排序方法

4. 输出结果

5. 退出界面

4.2错误信息

5. 算法复杂度和稳定性分析
下图反应了不一样算法排序时间复杂度等级及其空间复杂度和稳定性。
算法名称
平均时间
辅助空间
稳定性
冒泡排序
O(n2)
O(1)
是
选择排序
O(n2)
O(1)
否
插入排序
O(n2)
O(1)
是
归并排序
O(nlog2n)
O(n)
是
快速排序
O(nlog2n)
O(n)
否
堆排序
O(nlog2n)
O(1)
否
希尔排序
\
O(1)
否
下图表明了多种算法在不一样数据规模下，完成排序所消耗时间（毫秒为单位），从表中能够显然看出O(n2)排序算法比O(nlog2n)算法 时间多出几百上千倍，而且伴随数据数据规模增大时间比也会伴随增大；因为排序数据采取随机数，次序将被打乱，快速排序算法优于其它排序算法。
算法名称
1万
2万
3万
4万
5万
6万
7万
8万
9万
10万
冒泡排序
1442
5497
12206
21861
34017
49148
67394
88880
111939
139071
选择排序
199
816
1790
3254
5062
7166
9645
12636
16102
19643
插入排序
178
717
1628
2882
4458
6446
8822
11649
14547
17914
归并排序
3
6
9
12
15
18
22
26
28
33
快速排序
2
5
8
11
14
18
21
25
29
32
堆排序
3
7
12
16
19
23
26
30
34
37
希尔排序
3
8
11
15
24
24
29
35
40
41

6. 收获和致谢
经过这次课程设计作业我着实感受了一次编程乐趣，从中学到了不少知识， 即使全部说“程序＝数据结构＋算法”，但我们在学习利用数据结构编程之前，并没能深刻体会到这一点，直到这次课设实践。 我们感受最深一点是：以前用C编程，只是重视怎样编写函数能够完成所需要功效，似乎没有明确战术，只是凭单纯意识和简单语句来堆砌出一段程序。但现在编程感觉完全不一样了。在编写一个程序之前，自己能够综合考虑多种原因，首先选择自己需要数据结构，然后选定一个或多个存放结构来具体决定后面函数关键风格。最终在编写每一个函数之前，能够仔细斟酌比对，挑选出最适合目前情况算法。这么，即使在完整还没有写出来之前，自己心中已经有了明确原图了。这么无形中就提升了自己编写程序质量。我们还体会到深刻了解数据结构关键性。只有真正了解定义数据类型好处，才能用好这么一个数据结构。了解经典数据结构性质是很有用，它往往是编写程序关键。这次试验中我们也出现过部分错误。但我们经过反复调试后，发觉并做了修改，从而完成了此次课程设计。 在这次数据结构课程设计中，我此次题目是多种排序，排序实际上是编程设计中应用比较广泛知识，经过此次设计，我对部分基础内部排序有了很好了解和掌握，而且经过此次课程设计中程序运行结果很好了解了排序多种算法稳定性和时间复杂度，既巩固了课堂上学到排序理论，又为自己编程增强了实践。总而言之，在这次数据结构课程设计中，收获还是蛮多。也让自己对数据结构这门课程有了愈加好认识，相信在越来越多尝试以后，自己会不停进步不停提升。

7. 参考文件

1.《数据结构(C语言版)》 严蔚敏 清华大学出版社
2.《C语言程序设计》 丁峻岭 中国铁道出版社
3.《C程序设计》 谭浩强 清华大学出版社

8. 附件
程序源代码：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<map>
#include<ctime>
#include<queue>
#include<vector>
#include<set>
#include<cstdlib>
using namespace std;
const int N=1000010;
int data_num,data_array[N],data_arrayy[N];
int old[N],a[N],t;
//数据输入
int input_num()
{
printf("您要给多少个数排序？\n\t\t");
scanf("%d",&data_num);
srand(NULL);
printf("随机产生%d个数:\n\t\t",data_num);
for(int i=1;i<=data_num;i++)
{
data_array[i]=rand()%10000000;
printf("%d\n",data_array[i]);
old[i]=data_array[i];
printf("\n\t\t");
}
}//排序后数据输出 从大到小 data_num 1
int outnew0()
{
printf("排序后结果为:");
for(int i=data_num;i>=1;i--)
printf("%d%s",data_array[i],i!=1?" ":"\n");
}//排序后逆序数据输出 从小到大 1 data_num
int outnew1()
{
printf("排序后结果为:");
for(int i=1;i<=data_num;i++)
printf("%d%s",data_array[i],i!=data_num?" ":"\n");
}
//排序后数据输出 从大到小 data_num-1 0
int outnew2()
{
printf("排序后结果为:");
for(int i=data_num-1;i>=0;i--)
printf("%d%s",data_arrayy[i],i!=0?" ":"\n");
}//排序后逆序数据输出 从小到大 0 data_num-1
int outnew3()
{
printf("排序后结果为:");
for(int i=0;i<data_num;i++)
printf("%d%s",data_arrayy[i],i!=data_num-1?" ":"\n");
}//插入排序
void charu()
{
int i,j;
int temp;
printf("插入排序:\n");
for(i=1;i<=data_num;i++)
{
int temp=data_array[i];
for (j=i;j>0 && temp<data_array[j-1];j--)
{
data_array[j]=data_array[j-1];
}
data_array[j]=temp;
}
if(!t)
outnew0();
else
outnew1();
}//冒泡排序
void maopao()
{
int temp;
for(int i=1;i<=data_num;i++)
for(int j=i+1;j<=data_num;j++)
if(data_array[i]>data_array[j])
{
temp=data_array[i];
data_array[i]=data_array[j];
data_array[j]=temp;
}
}//选择排序
void chose_sort(int a[],int n)
{
int min,temp;
for(int i=0;i<n;i++)
{
min=i;
for(int j=i;j<n;j++)
if(a[min]>a[j])
min=j;
temp=a[min];
a[min]=a[i];
a[i]=temp;
}
}//堆排序
void HeapAdjust(int *a,int i,int size)//调整堆
{
int lchild=2*i;//i左孩子节点序号
int rchild=2*i+1;//i右孩子节点序号
int max=i;//临时变量
if(i<=size/2)//假如i是叶节点就不用进行调整
{
if(lchild<=size&&a[lchild]>a[max])
max=lchild;
if(rchild<=size&&a[rchild]>a[max])
max=rchild;
if(max!=i)
{
swap(a[i],a[max]);
HeapAdjust(a,max,size);//避免调整以后以max为父节点子树不是堆
}
}
}
void BuildHeap(int *a,int size)//建立堆
{
int i;
for(i=size/2;i>=1;i--)//非叶节点最大序号值为size/2
HeapAdjust(a,i,size);
}
void HeapSort(int *a,int size)//堆排序
{
int j=1;
BuildHeap(a,size);
for(int i=size;i>=1;i--)
{
swap(a[1],a[i]); //交换堆顶和最终一个元素，即每次将剩下元素中最大者放到最终面
//BuildHeap(a,i-1); //将余下元素重新建立为大顶堆
HeapAdjust(a,1,i-1); //重新调整堆顶节点成为大顶堆
}
}//快速排序能够选择用algorithm里sort排序实现
void kuaisu1()//快速排序1
{
printf("快速排序:\n");
sort(data_array+1,data_array+data_num+1);
if(!t)
outnew0();
else
outnew1();
}
void kuaisu2()//快速排序2
{
sort(data_array+1,data_array+data_num+1);
if(!t)
outnew0();
else
outnew1();
}//希尔排序
void ShellInsert(int *a,int d,int n)
{
for (int i=d;i<n;i++)//从第2个数据开始插入
{
int j=i-d;
int temp=a[i];//统计要插入数据
while(j >= 0&&a[j]>temp)//从后向前，找到比其小数位置
{
a[j+d]=a[j];//向后挪动
j-=d;
}
if(j!=i-d)//存在比其小数
a[j+d]=temp;
}
}
void ShellSort(int* a,int n)
{
int d=n/2;//初始增量设为数组长度二分之一
while(d>=1)
{
ShellInsert(a,d,n);
d=d/2;//每次增量变为上次二分之一
}
}//归并排序
void __merge(int a[],int first,int mid,int last,int temp[])
{
int i=first,j=mid+1,m=mid,n=last,k=0;
while(i<=m&&j<=n)
{
if(a[i]<=a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}
while(i<=m)
temp[k++]=a[i++];
while(j<=n)
temp[k++]=a[j++];
for(i=0;i<k;i++)
a[first+i]=temp[i];
}
void MergeSort(int a[],int first,int last,int temp[])
{
if(first<last)
{
int mid=(first+last)/2;
MergeSort(a,first,mid,temp);
MergeSort(a,mid+1,last,temp);
__merge(a,first,mid,last,temp);
}
}
bool MergeSort(int a[],int n)
{
int *p=new int[n];
if(p==NULL)
return false;
else
{
MergeSort(a,0,n-1,p);
delete[] p;
return true;
}
}//输出
void print()
{
printf("欢迎再次使用!!!\n\r\n");
printf("*******************************************\n");
printf("** . ..... . . ..... **\n");
printf("** . . . . . . **\n");
printf("** . . . . . ..... **\n");
printf("** . . . . . . **\n");
printf("** ..... ..... . ..... **\n");
printf("****************************