汽院数据结构第八次实验报告.doc

数据结构试验报告K3739刘X20__973049试验八排序技术的编程实现一：试验任务和要求

1.排序技术的编程实现，把握排序技术的编程实现，可以实现一种，也可以实现多种。也鼓舞同学利用基本操作进行一些应用的程序设计。

2.题目为设计一个押注的小嬉戏，计算机从到30之间产生5个数据。不显示出来，然后用户从键盘输入到30之间的5个数据，然后把两组结果都进行排序。两次排序最好启用不同的排序方式。

3.然后进行显示和对比，分别显示出本次相同的数据和个数以及不相同的数据和个数。存储结构自己设计。然后供应一种可以反复运行的机制，保证本程序可以运行。

二、原理分析和程序设计

1.希尔排序：

(1)选择一个步长序列step,step2,stepk,其中后一轮的步长一般为上一轮的一半，stepk=;

(2)按步长序列个数K,对序列进行K轮排序；

(3)每趟排序中，依据对应的步长stepi，将待排序列分割成若干长度为m的子序列，分别对各子表进行挺直插入排序。当步长因子为时整个序列作为一个表来处理。希X排序技术的原理示意图

2.快速排序：快速排序的思路是第一次把第一个数据换到它“正确位置”上，所谓正确位置是指它左边的全部的数据都比它小，它右边的数据都比它小，这样从最终盼望的结果看它的位置就是正确的，将待排空间按关键码以支点数据分成两部分称为一次划分，然后用递归的思想对于左右两边的数据连续排序，直到整个数据序列关键码有序排列。快速排序技术的原理示意图：590XXXX8977052XXXX6359897XXXX9520759XXXX7056395XXXX5989775XXXX2070559XXXX9639520XXXX0559(59)778963

4.归并排序技术：归并排序首先把任何一个数字都看成已经排好序的数据，之后把相邻的两个已排好空间进行合并，连续保持有序，这样全部已排空间就变成了长度为2的表，然后重复这个思路，不断成倍扩大这个空间的长度，直到全部数据都被合并在一起。归并排序技术的原理示意图：（59）

(1)

(30)（63）（0）

(7)（07）（05）（59）（3063）（07）（0507）（305963）（0（005XXXX7763）voidlist:mergecoutendl归并排序的过程显示为：endl;mergesort(data,total);cout归并排序的结果为：endl;for(inti=0;itotal;i+)coutdataiintlist:mergesort(intData,intn)intswap;int_divide递终止条件if(n=)return0数据分割divide=Data+n-;mergesort(Data,n-);mergesort(divide,)并数据并排序for(inti=0;i;i+)XXX）59for(intj=n--+i;j=0;j-)if(Datajdividei)break;swap=dividei;for(intk=n--+i;kj;k-)Datak+=Datak;Datak+=swap出结果for(i=0;itotal;i+)coutdataicoutendl;return0;

三、试验小结编程遇到的问题：在基数排序中感觉到自己所理解的理论和将它在程序代码中实现有肯定难度，在其他的排序中则是对比书本上的例题进行敲的，自己完全写则就显得难了些。但是看书写，自己力量也的确提高了些。

2试验收获及体会：程序需要花时间勤加练近平，当自己亲自动手去一个一个敲出来的代码在无形中自己力量就提高了。书上代码例题许多，花点时间敲一敲，还是值得的。

3不足之处及下一步需改进的地方：不足的地方有许多比如需要参照书本，改进的就就是需要针对图形整合自己的思想，读懂代码同时自己要编码的出来。