内容发布更新时间 : 2025/3/31 23:26:58星期一 下面是文章的全部内容请认真阅读。
第二部分：排序算法验证及评价
◎实验题目: 排序算法验证及评价（排序器）
◎实验目的：通过编写内部排序算法程序，加深排序算法的理解和掌握，同时对这四种算法在特定数据条件下的效率进行分析和评判，理解各个算法的效率优劣。
◎实验内容：实现以下六种排序算法，将给定的不同规模大小的数据文件（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,