数据结构课程设计报告

第二部分：排序算法验证及评价

◎实验题目: 排序算法验证及评价（排序器）

◎实验目的：通过编写内部排序算法程序，加深排序算法的理解和掌握，同时对这四种算法在特定数据条件下的效率进行分析和评判，理解各个算法的效率优劣。

◎实验内容：实现以下六种排序算法，将给定的不同规模大小的数据文件（data01.txt，data02.txt，data03.txt，data04.txt）进行排序，并将排序结果分别存储到sorted01.txt，sorted02.txt，sorted03.txt和sorted04.txt文件中。 1）、Shell排序； 2）、Quick排序 3）、锦标赛排序； 4）、堆排序 5）、归并排序； 6）、基数排序

在实现排序算法1）~4）时，统计数据元素比较的次数和交换的次数，进而对这四种算法在特定数据条件下的效率进行分析和评判。 一、程序形式

1． 本演示程序中，进入运行界面，程序提示输入操作（排序方式）和数据存放文件名，然后程序读入数据后建立顺序表，输入完毕后程序进行排序并输出到文件，同时统计比较和交换次数。

2． 程序执行的命令包括：

（1）输入要进行的操作和数据存放文件名 （2）读入数据构造顺序表 （3）进行排序 （4）输出结果到文件 （5）结束。 3． 程序数据存储格式：

45 (1) （数据及出现次数） 4． 运行界面：

二 概要设计

为了实现排序操作，可以以顺序表为数存储结构（各个不同的排序算法使用同样的顺序表）。 1.顺序表定义

typedef struct //存放数据及其出现次数 { int data; char c[5]; //出现次数最大999次 }node;

2.各函数及其作用

1). 希尔排序驱动及增量数组求解函数 void dlta(node *d,int num,int &jc,int &bc) 初始条件：存储数据顺序表已经建立

操作结果：求得增量数组和驱动希尔排序程序 2).希尔排序函数

void shellsort(node *d,int num,int dlt[],int t,int &jc,int &bc) 初始条件：存储数据顺序表已经建立和已经求得增量数组 操作结果：以递减增量进行shell排序 3).固定增量排序函数

void shellinsert(node *d,int num,int inc,int &jc,int &bc) 初始条件：存储数据顺序表已经建立和增量已给定 操作结果：以给定增量inc作一趟希尔排序 4).快速排序函数

void quicksort(node *d,int low,int high,int &jc,int &bc) 初始条件：存储数据顺序表已经建立

操作结果：对顺序表d中的从low到high的子列作快速排序 5).交换枢轴两边数据函数

int partition(node *d,int low,int high,int &jc,int &bc) 初始条件：存储数据顺序表d已经建立

操作结果：交换顺序表d中的从low到high的子表记录，使枢轴记录到位，并返回其所在位置，此时在它之前（后）的记录均不大（小）于它 6).锦标赛排序函数

void treesort(node *&d,node *r,int num,int &jc,int &bc) 初始条件：存储数据顺序表d已经建立

操作结果：将顺序表d中数据按树形选择进行排序 7).建立初始排序树函数

void treejust(node **t,node *d,int i,int num,int &jc,int &bc) 初始条件：存储数据顺序表d已经建立

操作结果：以d中数据建立最初的排序树，除叶子结点外，树的第i层存储在t[i]中 8).堆排序函数

void heapsort(node *d,int num,int &jc,int &bc) 初始条件：已经读入数据建立顺序表d 操作结果：对顺序表d进行堆排序 9).调大顶堆函数

void heapadjust(node *d,int s,int m,int &jc,int &bc)

初始条件: 已知d[s...m]中记录的关键字除之d[s]外均满足堆的定义 操作结果：调整d[s]的关键字，使成为一个大顶堆 10）.归并排序驱动函数

void mergesort(node *&d,int num)

初始条件：已经读入数据建立顺序表d 操作结果：对顺序表d作归并排序 11).归并排序递归函数

void msort(node *d,node *p,int s,int t)

初始条件：已经读入数据建立顺序表d 操作结果：将d[s...t]归并为p[s...t] 12).归并函数

void merge(node *rs,node *d,int i,int m,int n)

初始条件：rs[s...m]和rs[m+1...t]已经按关键字有序

操作结果：将有序rs[s...m]和rs[m+1...t]归并为有序的d[s...t] 13).基数排序函数

void radixsort(node *d,int num,int *r,int max)

初始条件：存储数据顺序表d和顺序号数组r已经建立

操作结果：对d作基数排序，其顺序号存储于r数组中，r[0]为头结点 14).关键字映射函数 int ord(int p,int i,node *d)

操作结果：将d[p]中第i个关键字映射到[0...9] 15).基数排序分配函数

void distribute(int *r,int i,int *f,int *e,node *d) 初始条件：存储数据顺序表d已经建立

操作结果：按d中各个数据第i个关键字建立RADIX各个子表，使同一子表中记录的第i个关键字相同

16).基数排序收集函数

void collect(int *r,int i,int *f,int *e)

初始条件：已按d中各个数据第i个关键字建立RADIX各个子表

操作结果：按第i个关键字自小至大地将f[0...9]所指各个子表依次链接成一个链表 17).主函数 void main()

初始条件：各个基本排序操作已经实现 操作结果：驱动各个排序函数 3． 本程序包含十七个模块： （1） 主程序模块：main()

（2） 希尔排序驱动及增量数组求解函数模块:dlta() （3） 希尔排序函数模块: shellsort（）

（4） 固定增量排序函数模块：shellinsert（） （5） 快速排序函数模块：quicksort（）

（6） 交换枢轴两边数据函数模块：partition（） （7） 锦标赛排序函数模块：treesort（） （8） 建立初始排序树函数模块：treejust（） （9） 堆排序函数模块：heapsort（）

（10） 调大顶堆函数模块：heapadjust（） （11） 归并排序驱动函数模块：mergesort（） （12） 归并排序递归函数模块：msort（） （13） 归并函数模块：merge（）

（14） 基数排序函数模块：radixsort（） （15） 关键字映射函数模块：ord（）

（16） 基数排序分配函数模块：distribute（） （17） 基数排序收集函数模块：collect（） 4.模块调用图：

主程序模块 main() 希尔排序驱动及增量数组求解模块:dlta() 快速排序函数模块： quicksort（） 锦标赛排序函数模块： treesort（） 堆排序函数块： heapsort（） 归并排序驱动模块：mergesort（） 基数排序函数模块： radixsort（） 希尔排序函数模块: shellsort（） 交换枢轴两边数据模块partition（） 建立初始排序树函数模块：treejust（） 调大顶堆函数模块：heapadjust（） 归并排序递归函数模块：msort（） 基数排序分配模块：distribute（） 基数排序收集函数模块：collect（） 固定增量排归并函数模关键字映射序模块：块：merge函数模块：shellinser（） ord（） t（） 详细设计见源码。 三、主要算法

1. Shell排序（缩小增量排序）：

希尔排序是对直接插入排序的改进。其改进出发点有二：一是插入时若关键字基本有序，则插入效率比较高。二是直接插入排序在数据个数很少时效率也比较高。故希尔排序的基本思想是：先将整个待排记录分割成若干子序列分别进行直接插入排序，待整个序列基本有序后，再对全体记录进行一次直接插入排序。其子序列是将相隔某个增量的记录组成一个