数据结构程序设计
内部排序算法比较
目录
摘 要 ........................................................................................................................... 1 1绪论 ............................................................................................................................ 1 2系统分析 .................................................................................................................... 1 2.1 功能需求 ............................................................................................................. 1 2.2数据需求 .............................................................................................................. 1 2.3 性能需求 ............................................................................................................. 2 3总体设计 .................................................................................................................... 2 3.1系统设计方案 ...................................................................................................... 2 3.2功能模块设计 ...................................................................................................... 2 4详细设计 .................................................................................................................... 3 4.1 数据结构定义 ..................................................................................................... 3 4.2伪随机产生数据模块 .......................................................................................... 4 4.3简单选择排序模块 .............................................................................................. 5 4.4起泡排序模块 ...................................................................................................... 6 4.5直接插入排序模块 .............................................................................................. 7 4.6希尔排序模块 ...................................................................................................... 8 4.7快速排序模块 ...................................................................................................... 9 4.8归并排序模块 .................................................................................................... 10 4.9条形图模块 ........................................................................................................ 11 5调试与测试 .............................................................................................................. 12 5.1 调试 ................................................................................................................... 12 5.2 测试 .................................................................................. 错误！未定义书签。 6结论 .......................................................................................................................... 13 结束语 ......................................................................................................................... 13 参考文献 ..................................................................................................................... 14 附录1－用户手册 ...................................................................................................... 15 附录2－源程序 .......................................................................................................... 17
I
数据结构程序设计
摘 要
本程序是比较几种排序算法的关键字比较次数和移动次数以取得直观感受。 内部算法有冒泡排序、直接插入排序、快速排序、希尔排序、归并排序等。每种算法都有自己的比较方法和优缺点，本程序能更直观的显示出各种排序的比较次数、移动次数和排序时间，并能用条形图（星号表示）进行表示，以便比较各种排序的优劣。该程序运用了数据结构中线性表的顺序存储结构和各种排序算法来共同实现的。
关键词：内部排序、条形图。 1绪论
随着科技的快速发展，越来越多的企业不再浪费人力财力去计算一些统计性结果，而是应用一些简单的程序或系统来完成这些任务。随着学习数据结构课程的深入，了解了不同排序算法的不同排序方法，每种排序对数据的比较次数、移动次数和排序用时都是不同的，本程序实现了六种内部排序算法的比较，并用条形图直观的显示出各种算法的优劣。运用伪随机产生的数据，调用六种排序算法，记录其比较次数、移动次数和排序时间，再分别用条形图（星号表示）表示出来。 2系统分析 2.1 功能需求
(1)对起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、归并排序算法进行比较。
(2)待排序的元素的关键字为整数，其中数据要用伪随机产生程序产生，并且至少用5组的输入数据做比较，再使用各种算法对其进行排序，记录其排序时间，再汇总比较。
(3)演示程序以人机对话的形式进行，每次测试完毕显示各种比较指标值，比较次数、移动次数和排序时间的列表，并用条形图即星号表示出来，以便比较各种排序的优劣。 2.2数据需求
抽象数据类型：线性表、排序算法 (1) 输入数据：需要比较的数据数目
1
数据结构课程设计
(2) 输出数据：不同算法的比较次数、移动次数、排序时间的数据以及对应的条形图。 2.3 性能需求
在运行本程序时，只要按照正确的操作方法不会出现无法运行的情况，系统稳定性好，安全，可靠，响应速度由需比较的数字数目多少来决定。 3总体设计 3.1系统设计方案
(1) 输入要排序的数据数目 (2) 抽象数据类型定义 typedef struct { int key;
}ElemType; //关键字 typedef struct {
ElemType *elem; int length;
}SqList;//分配顺序存储结构
(3) 存储结构：本程序采用了线性表的顺序存储结构。 (4) 算法设计：
简单选择排序：运用顺序表。时间复杂度O(n2)，空间复杂度O(1)。 起泡排序：时间复杂度O(n2)，空间复杂度O(1) 直接插入排序：时间复杂度O(n2)，空间复杂度O(1) 希尔排序：时间复杂度O(n1.3)，空间复杂度O(1) 快速排序：时间复杂度O(nlog2n)，空间复杂度O(nlog2n) 归并排序：时间复杂度O(nlog2n)，空间复杂度O(n) 3.2功能模块设计
根据分析整个程序主要划分为8个功能模块，分别执行要求中的功能。1个产生伪随机数据模块、6个内部排序算法模块以及1个形成条形图模块。功能模块图如图1所示
2
数据结构课程设计
内部排序算法比较系统伪随机产生数据简单选择排序起泡排序直接插入排序希尔排序快速排序 归并排序条形图表示比较结果图1功能模块图
(1)伪随机产生数据模块：本程序要求数据是要用伪随机产生程序产生，再用不同排序算法进行排序。
(2)简单选择排序模块：运用简单选择排序法对伪随机产生的数据进行排序。
(3) 冒泡排序模块：运用起泡排序法对伪随机产生的数据进行排序。 (4)直接插入排序模块：运用直接插入排序法对伪随机产生的数据进行排序。
(5)希尔排序模块：运用希尔排序法对伪随机产生的数据进行排序。 (6)快速排序：运用快速排序法对伪随机产生的数据进行排序。 (7)归并排序：运用归并排序法对伪随机产生的数据进行排序。 (8)条形图表示比较结果：统计6种排序算法的比较结果，用条形图表示出来。 4详细设计 4.1 数据结构定义
typedef struc {int key;
}ElemType; //关键字
3