《数据结构》课程设计报告---排序算法的实现与比较

《数据结构》课程设计报告

排序算法的实现与比较

设计内容及要求

编程实现插入、希尔、快速、堆排序、归并排序算法，并计算每种算法的比较、交换次数。将待排数据从磁盘文件读入，实施排序后将数据写入另一个文件中。

概述

在本设计课题中，我们将对常见的5中排序算法——插入、希尔、快速、堆排序、归并排序进行各种情况下的比较，如待排数据为顺序、逆序或随机的情况下，各个算法对于特定数据的性能。基于此点考虑，在程序中选择采用以毫秒为单位的执行时间来衡量算法对特定数据的性能高低。本文将主要介绍《排序之谜》程序（以下简称“程序”）的数据结构的设计、功能设计以及相关技术讨论等。本程序在Microsoft Windows Server 2003/Microsoft Visual C++ 2005的命令行编译器cl.exe环境编译下通过。

分发包说明

程序分发包中将包含以下文件，其用途分别如表格1所示。

文件名 说明 algorithm_lib.h 头文件，包含所有排序算法的实现 functions.h main.cpp makefile sort.exe src.dat report.pdf 头文件，包含所有程序调用函数的实现 C++源文件，包含主程序界面的实现 Makefile，包含源文件间依存关系及自动化编译选项 Windows二进制可执行程序 数据文件，包含一组测试用数据 PDF文档，即本设计报告 表格1 数据结构设计

主程序数据结构

主程序中采用两个整型数组input_array和output_array，其长度均为10000，分别作为待排序数据和已排序数据的存放空间，并设置一整型数组sort_time用来存放5个算法的执行时间。

《数据结构》课程设计报告

之所以这样设计，是因为所有的用户定义函数都完全按照既定的“标准”设计实现，使得整个程序的可伸缩性大大增强。

#define LENGTH 10000 int length = LENGTH; int input_array[LENGTH] = {0}; int output_array[LENGTH] = {0}; int sort_time[5] = {0}; // 0 InsertionSort, 1 QuickSort, 2 MergeSort, // 3 HeapSort, 4 ShellSort 排序算法的设计实现

程序中的全部5中排序算法均按照标准化的函数名、返回值和形参表设计，其形式为：

voidSomeSortMethod(constint *array_to_sort,int *sorted_array,constint length); 算法的设计和实现参照了现有教科书1上的算法描述，下面将逐一列出各个排序算法的C++实现。 插入排序

插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的有序表。

void InsertionSort(constint *array_to_sort, int *sorted_array, constint length) { for (int i = 0; i < length; i++) { sorted_array[i] = array_to_sort[i]; } int i = 0, j = 0; int key = 0; for (j = 1; j < length; j++) { key = sorted_array[j]; i = j - 1; while (i >= 0 && sorted_array[i] > key) { sorted_array[i + 1] = sorted_array[i]; i--; } sorted_array[i + 1] = key; } } 快速排序

1

参见：参考资料[2]和[3]。

1

《数据结构》课程设计报告

快速排序是对冒泡法排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录均比另一部分记录小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

void quicksort(int v[], int left, int right) { int i, last; void swap(int v[], int i, int j); if (left >= right) return; swap(v, left, (left + right)/2); last = left; for (i = left + 1; i <= right; i++) if (v[i] < v[left]) swap(v, ++last, i); swap(v, left, last); quicksort(v, left, last-1); quicksort(v, last+1, right); } void QuickSort(constint *array_to_sort, int *sorted_array, constint length) { for (int i = 0; i < length; i++) { sorted_array[i] = array_to_sort[i]; } quicksort(sorted_array, 0, length - 1); } 归并排序

归并排序的核心操作是将一位数组中前后两个相邻的有序序列归并为一个有序序列，其实现如下：

void merge(int *src, int *dest, int lo, int mid, int hi) { int j = 0, k = 0; for (j = mid + 1, k = lo; lo <= mid && j <= hi; k++) { if (src[lo] <= src[j]) dest[k] = src[lo++]; else dest[k] = src[j++]; } if (lo <= mid) { while (k <= hi) { dest[k] = src[lo]; k++; lo++; } }

2

《数据结构》课程设计报告

} if (j <= hi) { while (k <= hi) { dest[k] = src[j]; k++; j++; } } 而归并排序则是递归的调用上述归并算法，将整个无序序列拆分成n个单个元素后两两归并为相邻的有序序列，依次递归的执行下去，最终归并为一个有序序列。其实现如下：

void MSort(int *src, int *dest, int start, int end) { int dest2[10000] = {0}; if (start == end) dest[start] = src[start]; else { int mid = (start + end) / 2; MSort(src, dest2, start, mid); MSort(src, dest2, mid + 1, end); merge(dest2, dest, start, mid, end); } } void MergeSort(constint *array_to_sort, int *sorted_array, constint length) { for (int i = 0; i < length; i++) { sorted_array[i] = array_to_sort[i]; } MSort(sorted_array, sorted_array, 0, length - 1); } 希尔排序

希尔排序2是一种插入排序类的方法，但在时间效率上较传统的插入排序方法有较大的改进。其主要特点是，子序列的构成不再是简单的“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列。其实现如下：

void shellsort (int *a, int n) { int i, j, k, h, v; int cols[] = {1391376, 463792, 198768, 86961, 33936, 13776, 4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1}; for (k = 0; k < 16; k++) { h = cols[k]; for (i = h; i < n; i++) { v = a[i]; 2

希尔排序也称作“缩小增量排序” （Diminishing Increment Sort）。

3