数据结构实验报告
K1373-4-19 刘洋 20139730419
实验八 排序技术的编程实现
一：实验任务和要求
排序技术的编程实现，掌握排序技术的编程实现，可以实现一种，也可以实现多种。也鼓励学生利用基本操作进行一些应用的程序设计。
题目为设计一个押注的小游戏，计算机从1到30之间产生5个数据。不显示出来，然后用户从键盘输入1到30之间的5个数据，然后把两组结果都进行排序。两次排序最好启用不同的排序方式。
然后进行显示和对比，分别显示出本次相同的数据和个数以及不相同的数据和个数。存储结构自己设计。然后提供一种可以反复运行的机制，保证本程序可以运行。
二、原理分析和程序设计
1.希尔排序：
（1）选择一个步长序列step1,step2,…,stepk,其中后一轮的步长一般为上一轮的一半，stepk=1;
（2）按步长序列个数K,对序列进行K轮排序；
（3）每趟排序中，根据对应的步长stepi，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。当步长因子为1时整个序列作为一个表来处理。
希尔排序技术的原理示意图
2.快速排序：
快速排序的思路是第一次把第一个数据 换到它“正确位置”上，所谓正确位置是指它左边的所有的数据都比它小，它右边的数据都比它小，这样从最后希望的结果看它的位置就是正确的，将待排空间按关键码以支点数据分成两部分称为一次划分，然后用递归的思想对于左右两边的数据继续排序，直到整个数据序列关键码有序排列。
快速排序技术的原理示意图：
[59 01 17 63 59 89 77 05 21 95]
[21 01 17 63 59 89 77 05 59 95]
[21 01 17 59 59 89 77 05 63 95]
[21 01 17 05 59 89 77 59 63 95]
[21 01 17 05 59 59 77 89 63 95]
[21 01 17 05 59] (59 ) [77 89 63 95]
4.归并排序技术：
归并排序首先把任何一个数字都看成已经排好序的数据，之后把相邻的两个已排好空间进行合并， 继续保持有序，这样所有已排空间就变成了长度为2的表，然后重复这个思路，不断成倍扩大这个空间的长度，直到全部数据都被合并在一起。
归并排序技术的原理示意图：
（59） （11） （30） （63） （01） （17） （07） （05）
（11 59） （30 63） （01 17） （05 07）
（11 30 59 63） （01 05 07 17）
（01 05 07 11 17 30 59 63）
void list::merge (){
cout<<endl<<"归并排序的过程显示为："<<endl;
mergesort(data,total);
cout<<"归并排序的结果为："<<endl;
for(int i=0;i<total;i++)
cout<<data[i]<<' ';
}
int list::mergesort (int Data[],int n){
int swap;
int *divide;
//传递终止条件
if(n==1)
return 0;
//对数据分割
divide=Data+n-n/2;
mergesort(Data,n-n/2);
mergesort(divide,n/2);
//合并数据并排序
for(int i=0;i<n/2;i++)
{
for(int j=n-n/2-1+i;j>=0;j--)
if(Data[j]<divide[i])
break;
swap=divide[i];
for(int k=n-n/2-1+i;k>j;k--)
{
Data[k+1]=Data[k];
}
Data[k+1]=swap;
//输出结果
for(i=0;i<total;i++)
cout<<data[i]<<' ';
cout<<endl;
}
return 0;
}
三、实验小结
1 编程遇到的问题：在基数排序中感觉到自己所理解的理论和将它在程序代码中实现有一定难度，在其他的排序中则是对照书本上的例题进行敲的，自己完全写则就显得难了些。但是看书写，自己能力也确实提高了些。
2 实验收获及体会 ：程序需要花时间勤加练习，当自己亲自动手去一个一个敲出来的代码在无形中自己能力就提高了。书上代码例题很多，花点时间敲一敲，还是值得的。
3 不足之处及下一步需改进的地方：不足的地方有很多比如需要参照书本，改进的就就是需要针对图形整合自己的思想，读懂代码同时自己要编码的出来。