数据结构课程设计--内部排序演示

《数据结构课程设计--内部排序演示》由会员分享，可在线阅读，更多相关《数据结构课程设计--内部排序演示（19页珍藏版）》请在毕设资料网上搜索。

1、 课程设计题目：课程设计题目：内部排序演示内部排序演示 1.问题描述问题描述-1 2.需求分析需求分析-1 3.数据结构设计数据结构设计-1 4.算法设计算法设计-1 1）概要设计）概要设计-1 2）详细设计）详细设计-2 5.测试分析测试分析-7 6.总结总结-8 7参考文献参考文献-9 8.附录：带注释的源程序附录：带注释的源程序-10 1.问题描述：问题描述：随着计算机技术的发展，各种排序算法不断的被提出。排序算法在计算机 科学中有非常重要的意义， 且应用很广泛。 在以后的发展中排序对我们的学习和生活的影响 会逐渐增大，很有必要学习排序知识。此次课程设计就是运用自己掌握排序的知识， 设计

2、一个测试程序比较几种排序算法的关键字比较次数和移动次数以取得直观感受。 2.需求分析需求分析： （1）实现各种内部排序。包括直接插入排序，希尔排序，冒泡排序，快速 排序，直接选择排序，归并排序，堆排序。 （2）待排序的元素的关键字为整数或（字符） 。可用随机数据和用户输入数据作测试比 较。 比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换以3次计)。 （3）演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标值的列表，以 便比较各种排序的优劣。 3数据结构设计数据结构设计 struct count int compare ; int move ; ; 4.算算法设计法设计

3、 1）概要设计）概要设计 主程序： int main() 初始化； while() 接受命令； 处理命令； 退出； 2）详细设计）详细设计 （1）冒泡排序 核心思想：设排序表中有 n 个数据元素。首先对排序表中第一，二个数据元素的关键字 array0和 array1进行比较。如果前者大于后者，则进行交换；然后对第二，三个数据做同 样的处理；重复此过程直到处理完最后两个相邻的数据元素。我们称之为一趟冒泡，它将关 键字最大的元素移到排序表的最后一个位置，其他数据元素一般也都向排序的最终位置移 动。然后进行第二趟排序，对排序表中前 n-1 个元素进行与上述同样的操作，其结果使整个 排序表中关键字次大

4、的数据元素被移到 arrn-2的位置。如此最多做 n-1 趟冒泡就能把所有 数据元素排好序。 核心代码：int array_size=0; void BubleSort(int array, int length) BubleSortCpare = 0 ; BubleSortCount.move = 0 ; int tmp; for(int j = length; j1; j-) for(int i =1;iarrayi) tmp = arrayi-1 ; arrayi-1 = arrayi; arrayi = tmp ; BubleSortCount.move+ ; （2）直接插入排序）直接插入排序 开始时把第一个数据元素作为初始的有序序列， 然后从第二个数据元素开始依次把数据元素 按关键字大小插入到已排序的部分排序表的适当位置。当插入第 i(1=0;j-) filterdown(array, j, len ); /初始建堆 for(int i=len-1;i=1;i-) int tmp ; tmp = array0 ; array0 = arrayi ; arrayi = tmp ; HeapSortCount.move+ ; len-; filter