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

数据结构实验报告 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 (){ coutendl归并排序的过程显示为：endl; mergesort(data,total); cout归并排序的结果为：endl; for(int i=0;itotal;i++) coutdata[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;in/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;kj;k--) { Data[k+1]=Data[k]; } Data[k+1]=swap; //输出结果 for(i=0;itotal;i++) coutdata[i] ; coutendl; } return 0; } 三、实验小结 1 编