数据结构排序实验报告

1、数据结构?课程设计报告实验五 排序一、需求分析：本演示程序用 C+6.0 编写，完成各种排序的实现，对输入的一组数字实现不同的排序 方法，对其由小到大顺序输出。1分别对直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序算法 进行编写。 2、对存储的函数即输入的数字进行遍历。3、初始化函数对输入的数字进行保存。4、主函数实现使用者操作界面的编写，对输入、选择、保存、输出的各种实现。 这当中还包括了各个函数的调用的实现。5、程序所能到达的功能：完成对输入的数字的生成，并通过对各排序的选择实现数字从小到大的输出。二、程序主要功能以及根本要求：1、设计一个菜单，格式如下：1、直接插入排序2、

2、希尔排序3、冒泡排序4、快速排序5、选择排序6、堆排序7、退出2、选择不同的菜单但进行相应的排序，并给出排序的关键字序列。三、系统框架图：本程序包含了 9个函数，它们分别是：1、直接插入排序的算法函数InsertSort 。各对输操作个入的界面排数组的设序进行计，函算遍历数的法初始调用。函化数主函数2、希尔排序的算法函数ShellSort。3、冒泡排序算法函数BubbleSort 。4、快速排序的算法函数Partition 。5、选择排序算法函数SelectSort。6、堆排序算法函数 HeapAdjust 。7、对存储数字的遍历函数Visit。8、初始化函数 InitSqList 。9、主函

3、数 main。四、详细设计实现各个算法的主要内容，下面是各个函数的主要信息:1各个排序函数的算法：一、直接插入排序void InsertSort(SqList &L)int i,j;for( i=2; i<=L.length;i+)if(L.ri.key < L.ri-1.key)L.r0 = L.ri;L.ri = L.ri-1;for( j=i-2; (L.r0.key < L.rj.key); j-)L.rj+1 = L.rj;L.rj+1 = L.r0;二、希尔排序void ShellSort(SqList &L)int i, j;int dk = 1

4、;/ 增量while(dk <=L.length/3)dk = 3*dk+1;/ 增大增量while(dk>0)dk /= 3;/ 减小增量for (i = dk; i <=L.length; i+)L.r0.key = L.ri.key;j = i;while (j >= dk) && (L.rj-dk.key > L.r0.key)L.rj.key = L.rj-dk.key;j -= dk;L.rj.key = L.r0.key;三、冒泡排序void BubbleSort(SqList &L)int i,j;for(i=0;i<

5、L.length-2;i+)int flag = 1;for(j=0;j<L.length-i-2;j+)if(L.rj.key > L.rj+1.key)flag = 0;int temp;temp = L.rj.key;L.rj.key = L.rj+1.key;L.rj+1.key = temp;/假设无交换说明已经有序if(flag=1)break;四、快速排序int Partition(SqList &L,int low,int high)/分割区域函数个元素作为支点L.r0 = L.rlow;int pivotkey = L.rlow.key;/ 一般将顺序表第

6、一 while(low < high)while(low<high && L.rhigh.key>=pivotkey) high-;L.rlow = L.rhigh;while(low<high && L.rlow.key<=pivotkey)low+;L.rhigh = L.rlow;L.rlow = L.r0;/ 返回枢轴位置return low;void QSort(SqList &L,int low,int high)/每张子表的快速排序if(low<high)int pivotloc = Partition(

7、L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);void QuickSort(SqList &L)QSort(L,1,L.length);五、简单项选择择排序void SelectSort(SqList &L)int min;int j;for (int i = 0; i <L.length; i+) / 选择第 i 小的记录，并交换j = i;min = L.ri.key;for (int k = i; k < L.length; k+) / 在 Ri.n-1 中选择最小的记录 if (L.

8、rk.key < min)min = L.rk.key ;j = k;if (i != j) / 与第 i 个记录交换 int temp = L.ri.key; L.ri.key = L.rj.key; L.rj.key = temp;六、堆排序void HeapAdjust(HeapType &H,int s,int m)/堆调整，将记录调整为小顶堆int j;RedType rc = H.rs;/ 暂时存储根结点for(j=2*s; j<=m; j*=2)/沿着结点记录较小的向下筛选if(j<m && H.rj.key<H.rj+1.key)

9、+j;if(rc.key>= H.rj.key)break;H.rs = H.rj;s = j;H.rs = rc;void HeapSort(HeapType &H)int i;RedType temp;for(i = H.length; i>0; -i)HeapAdjust(H,i,H.length);for(i=H.length; i>1; -i)temp = H.r1;H.r1 = H.ri;H.ri = temp;HeapAdjust(H,1,i-1);2遍历函数与初始化void Visit(SqList L)for(i nt i=1; i<=Len

10、gth; i+) cout<<L.ri.key<<""cout<<e ndl;void InitSqList(SqList &L,int a)for(i nt i=1;i<=Len gth;i+) L.ri.key = ai;五、测试结果以下是各种界面的测试结果:1输入的界面"E:石門序理資Debu gV? E予e氓'RH 2 s S 3 6S 7 2 4 熱姝 ? 1 2 3 4 5 AAAAAA -一 - _扌丄1牛七1扌孑 请请谙请请排序操作界面肮量脣的儼直设计9訪ug瞬序尼“'WSS 9.1

11、选直希曰届选亠-n1234567游界面排序iM耳 N X 3*X W 耳 N X 3*X W 耳？请输入你需要的操作:3各种排序的结果:菲序后敎字序列2 23 4£ 鬧 76轍操作23 46坯丿予刖炎Eft排序后数字序列；12 23 46 59 76 任菖撻继绩1 请希人你需要的操作IE序前裁字序列=2 58 76 23 46菲序后数字序列I攏詁52 S8 76 23 46非序后数字序列：3 4& 58 76 46盍匾入祢需要的罠作：6 距岸前记录序列；2 58 7B 23 怖 丰序后i酥序列=2 23 4G GS ?fcF序后数字序列七i翱姑谍輕设计、。出四也時，晞六、设计缺乏以及存在问题本程序是基于