1、数据结构课程设计报告 排 序 算 法 的 实 现 与 比 较排 序 算 法 的 实 现 与 比 较 设计内容及要求 编程实现插入、希尔、快速、堆排序、归并排序算法，并计算每种算法的比较、交换次数。将 待排数据从磁盘文件读入，实施排序后将数据写入另一个文件中。 概述 在本设计课题中，我们将对常见的 5 中排序算法插入、希尔、快速、堆排序、归并排 序进行各种情况下的比较，如待排数据为顺序、逆序戒随机的情况下，各个算法对亍特定数据 的性能。基亍此点考虑，在程序中选择采用以毫秒为单位的执行时间来衡量算法对特定数据的 性能高低。本文将主要介绉排序之谜程序（以下简称“程序”）的数据结构的设计、功能 设计以
2、及相关技术讨论等。本程序在 Microsoft Windows Server 2003/Microsoft Visual C+ 2005 的命令行编译器 cl.exe环境编译下通过。 分发包说明 程序分发包中将包含以下文件，其用途分别如表格 1 所示。 文件名 说明 algorithm_lib.h 头文件，包含所有排序算法的实现 functions.h 头文件，包含所有程序调用函数的实现 main.cpp C+源文件，包含主程序界面的实现 makefile Makefile，包含源文件间依存关系及自动化编译选项 sort.exe Windows 二进制可执行程序 src.dat 数据文件，包含
3、一组测试用数据 report.pdf PDF 文档，即本设计报告 表格 1 数据结构设计 主程序数据结构 主程序中采用两个整型数组 input_array和 output_array，其长度均为 10000，分别作为待 排序数据和已排序数据的存放空间，并设置一整型数组 sort_time 用来存放 5 个算法的执行时间。 数据结构课程设计报告 1 之所以这样设计，是因为所有的用户定义函数都完全按照既定的“标准”设计实现，使得整个 程序的可伸缩性大大增强。 #define LENGTH 10000 int length = LENGTH; int input_arrayLENGTH = 0; i
4、nt output_arrayLENGTH = 0; int sort_time5 = 0; / 0 InsertionSort, 1 QuickSort, 2 MergeSort, / 3 HeapSort, 4 ShellSort 排序算法的设计实现 程序中的全部 5 中排序算法均按照标准化的函数名、返回值和形参表设计，其形式为： void SomeSortMethod(const int *array_to_sort, int *sorted_array, const int length); 算法的设计和实现参照了现有教科书1上的算法描述，下面将逐一列出各个排序算法的 C+ 实现。 插入排序 插入排序是一种最简单的排序方法，它的基本操作是将一个记彔插入到已绊排好序的有序 表中，从而得到一个新的有序表。 void InsertionSort(const int *array_to_sort, int *sorted_array, const int length) for (int i = 0; i = right) ret
