数据结构设计报告 [文档在线提供].docVIP

一：题目要求 1．实现基本排序方法：直接插入、希尔、直接选择、冒泡、快速、堆、二路归并； 2．对每种基本排序方法尽量给出改进算法； 3．给出改进前后的实验结果： （1）随机生成若干个随机数进行排序（如n＝103，2＊103，104，…等）celeron1.8GHz 内存：DDR256M 主板：EPX 操作系统：Windows 98 编译软件：C＋＋6.0 n 方法 3*104 6*104 9*104 11*104 12*104 13*104 14*104 15*104 105 正序 逆序 直接插入排序 2.58 9.28 20.21 36.86 36.36 76.35 88.76 122.54 0 84.2 改进折半插入 1.48 8.24 16.59 29.22 30.87 53.44 65.86 84.59 0 68.11 冒泡排序 9.07 31.03 61.18 91.72 101.77 223.82 240.08 272.16 70.96 167.9 改进含标志冒泡 9.00 30.83 72.17 80.52 99.68 200.42 220.25 249.594 0 141.33 直接选择排序 3.35 15.33 32.52 52.78 56.3 76.35 82.557 189.33 68 71.9 改进2路选择 1.7 7.08 15.6 25.49 27.85 50.02 74.567 83.81 32.46 52.29 Shell排序 0.05 0.22 0.16 0.06 0.11 0.22 0.27 0.22 0.05 0.05 快速排序 0.01 0.01 0.11 0.16 0.16 0.27 0.38 0.33 0.22 0.22 归并排序 0.01 0.03 0.10 0.04 0.07 0.18 0.07 0.08 0.03 0.03 改进非递归归并 0.01 0.04 0.09 0.061 0.081 0.14 0.111 0.121 0.05 0.05 堆排序 0.02 0.05 0.6 0.27 0.55 0.22 0.22 0.77 0.44 0.66 三：设计和改进思路 1、直接插入排序的基本思想是： 2、:改进折半插入排序的基本思想是：直接排序的基本思想是：排序的基本思想是：直接排序的基本思想是： 排序的基本思想是：直接排序排序的基本思想是：先将待排序记录的序列按某个间隔长度分割成为若干个子序列分别进行直接插入排序，重复进行数据分割，每次分割的间隔长度逐步缩小，直到最后间隔长度为1时，对全体记录进行一次直接插入排序，这时所有记录按关键字有序，排序结束。增量序列的选择??? 　Shell排序的执行时间依赖于增量序列。??? 　好的增量序列的共同特征：　最后一个增量必须为1；　 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。??? 　有人通过大量的实验，给出了目前较好的结果：当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。Shell排序的时间性能优于直接插入排序??? 　希尔排序的时间性能优于直接插入排序的原因：　　当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。　　当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。　　在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。??? 　因此，希尔排序在效率上较直接插人排序有较大的改进。稳定性??? 　希尔排序是不稳定的。两个相同关键字在排序前后的相对次序发生了变化。 8、快速排序的基本思想是： ９、改进快速排序的基本思想是: １０、选择排序排序的基本思想是： 9:堆排序的基本思想是：10、归并排序基本思想和改造： 是通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度;归并排序的基本思想是：将两个或两个以上的有序子序列“归并”为一个有序序列。 在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列 归并为一个有序序列。 “归并”算法描述如下： templateclass Elem void Merge (Elem SR[], Elem TR[], int i, int m, int n) { // 将有序的SR[i..m]和SR[m+1..n]归并为 // 有序的TR[i..n] for (