《数据结构课程设计报告最新》由会员分享，可在线阅读，更多相关《数据结构课程设计报告最新（28页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计实验报告尹浩宇一、 需求分析 本课程设计需要实现的是对集中内部排序算法的时间复杂度、比较次数和交换次数进 行分析。通过分析，选择了 8 种比较典型的内部排序算法作为目标算法进行测试，记录排 序所花费的时间、交换比较次数，在画出相应的图标进行分析。 二、 概要设计 考虑到方便初始化等原因，将所有的排序算法看做继承同一基类的对象。采用 c/c+语 言进行该程序的设计。将所有的排序算法看作一个对象，从虚基类 Sort 中继承方法和数据， 统一使用 Sort 指针进行测试。将所得结果以文本形式保存在文件中，之后使用 excel 等工 具绘制相关的图形并进行分析。另外，测试数组的规模从
2、10k 随机增加到 100k。 三、 详细设计 （其他排序算法的类类似，在此不一一赘述）四、 排序算法结果比较测试的排序算法包括：直接插入排序(Insert Sort) 、希尔排序(Shell Sort)、起泡排序(Bubble Sort)、快速排序(Quick Sort)、简单选择排序(Selection Sort) 、堆排序(Heap Sort)和并归排序 (Merging Sort)七种。 直接插入排序（Insert Sort） 即是将整个数组分为两个部分，一部分是已经有序的数组，剩余的是待排序的数组。 对每一个在待排序数组中的元素，相当于在一个已排好序的数组 a0n中插入一个数据 e，
3、使得 a0.n+1 仍然为一个有序的数组。待排序的数组长度为 0 的时候排序完成。 算法如下： virtual void Insert_Sort(int *a,int len) int temp,j; for (int i = 0; i aj j -= 1; aj + 1 = temp; /end for /end Insert_Sort() 由分析，对于每一个在数组 a 的元素都需要在已排好序的数组中寻找其应该在的位置， 最坏的情况即完全逆序下 ai需要比较 i 1 次，总共需要比较的次数为 即 n*(n-1)/2 1 1 次，即是一个 O( ) 的时间复杂度。但是在逆序的情况下该算法只需要
4、简单遍历数组即可， 2 即是一个 O(n)的时间复杂度。对于随机的情况，更具概率相同的原理，其时间复杂度应仍 然是 O( )，但排序所需时间应该是完全逆序情况下的一半。 2 以下是对算法运行时间、比较次数、交换次数的记录图表：0 20000 40000 60000 80000 100000 120000 0 5 10 15 20 25 30 RANDOM REVERSE ORDERLY Insert Sorting-Time 0 20000 40000 60000 80000 100000 120000 0 200000000 400000000 600000000 800000000 1E+
5、9 1.2E+9 1.4E+9 1.6E+9 1.8E+9 RANDOM REVERSE ORDERLY Insert Sorting-Exchange 0 20000 40000 60000 80000 100000 120000 0 200000000 400000000 600000000 800000000 1E+9 1.2E+9 1.4E+9 1.6E+9 1.8E+9 RANDOM REVERSE ORDERLY Insert Sorting-Compare 其结果大致符合理论得出分析的结论。另外，该结果也反映出该算法不是一个稳定的排序算法。希尔排序(Shell Sort) 在直接
6、插入排序中，不必要的交换过多，并且我们可以发现若待排序的数组已经基本 有序，使用插入排序是很快的。希尔排序是利用上述规律对直接插入排序的一种改进，将 规模较大数组分为规模小的部分排序，待数组基本有序之后进行直接插入排序。 其算法如下： void Shell_Sort(int *a,int len) for(int div = len / 2;div = 1;div /= 2) /Set div and reduce for(int i = div;i = 0;j -= div) /Sort arr with few elems if(aj = high) return;int first =
7、low;int last = high;int key = afirst;while(first = key)-last;afirst = alast;while(first aj) min = j; if(min != i)swap(amin,ai); i = 0; / while(i = Ai 。在数组的非降序 排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。从 而完成排序。 对于堆排序，他的平均时间复杂度为 O(n*logn)。 算法实现如下： void HeapAdjust(int array,int i,int nLength)int nChild;int nTemp;for(;2*i+1nLength;i=nChild)nChild=2*i+1;
