第 1 页
数据结构的课程设计
课程名称： 课程设计题目： 姓名： 学院： 专业： 年级：
学号：
日期
年 月 日
第 1 页 共 1 页
第 2 页
排序算法课程设计题1
一、问题描述
排序算法是对一系列无序的数据进行排序，使之有序，根据算法思想及程序设计的不同，有多种排序算法：希尔排序、快速排序、堆排序、归并排序等。 二、几种排序算法的思想描述
? 希尔排序：该排序算法是在直接插入排序算法的基础上改进的,选取小于数据个数一个
整数d作为增量，将所有的数据分成d组，现在各组内进行直接插入排序，然后取第二个增量进行重复的分组和排序。
? 快速排序：是对冒泡排序算法对的一种改进，选择一个枢轴，其前面的数全都比其小，
后面的数据全都比其大。然后对两部分的数据进行相应的快速排序。 ? 堆排序：与完全二叉树相对应
? 归并排序：将两个有序的序列归并成为一个对应的有序的序列。 三、总体设计
各种排序算法的实现其实就是函数的实现，在一个头文件中实现，而在主函数中可以设置一个菜单函数来提供选择项，供用户选择选择项来选择使用哪个函数来进行排序，其中随机产生数据可以通过函数rand函数来实现，并且还涉及到对文件进行操作。
设计步骤
主函数void main()函数
调用rand()函数来产生1000个数 据，并同时存入磁盘文件中
从磁盘文件中读取数据到程序的数组中 序择函数进行排 通过菜单项选1.希尔排序 2.快速排序 3.堆排序 4.归并排序 将排序结果存入磁盘文件中
第 2 页 共 2 页
第 3 页
四、详细设计
? 模块一、函数头文件
#include
? 模块二、主函数void main() ? 模块三、子函数
? 希尔排序：void ShellSort(int r[],int n) ? 快速排序：int Partion(int r[],int i,int j); void QuickSort(int r[],int i,int j)
? 堆排序：void Sift(int r[],int k,int m);void HeapSort(int r[],int n) ? 归并排序：void Merge(int r[],int r1[],int s,int m,int t) void MergePass(int r[],int r1[],int n,int h) void MergeSort(int r[],int n)
? 菜单选择项函数：int Menu()； ? 随机产生数据的函数：void generate(int *array_to_sort,const int length); ? 将数据写入磁盘文件的函数：bool write(int *array, int length, const
char*file_name);
从磁盘文件读入数据的函数：bool read(int *array, int length, const char *file_name);
? 从磁盘文件读入数据的函数：bool read(int *array,int length,const char
*filename);
void Sort(int *r,int n,int m);
进行排序的总函数：void Sort(int *r,int n,int m); ? 数据输出的函数：void Printm(int *r,int n); 五、实例代码
包含四种排序函数的头文件：Sort.h //希尔排序算法
void ShellSort(int r[],int n); //快速排序算法
int Partion(int r[],int i,int j); void QuickSort(int r[],int i,int j); //堆排序算法
void Sift(int r[],int k,int m); void HeapSort(int r[],int n); //归并排序算法
void Merge(int r[],int r1[],int s,int m,int t); void MergePass(int r[],int r1[],int n,int h); void MergeSort(int r[],int n);
//四种排序函数实现的源文件：Sort.cpp #include \#include
void ShellSort(int r[],int n
?
第 3 页 共 3 页
第 4 页
{
int d,i,j; int temp;
for(d=n/2;d>=1;d=d/2) for(i=d+1;i<=n;i++) {
temp=r[i];
for(j=i-d;j>=1&&temp //快速排序算法 int Partion(int r[],int i,int j) { int temp=r[i]; while(i while(i if(i r[i]=temp; return i; } void QuickSort(int r[],int i,int j) { if(i int pivot=Partion(r,i,j); QuickSort(r,i,pivot-1); QuickSort(r,pivot+1,j); } } //堆排序算法 void Sift(int r[],int k,int m) { int i=k,j=2*i; int temp; while(j<=m) { if(j 第 4 页 共 4 页 第 5 页 if(r[i]>=r[j]) break; else { temp=r[i]; r[i]=r[j]; r[j]=temp; i=j;j=2*i; } } } void HeapSort(int r[],int n) { int d,i; int temp; for(d=n/2;d>=1;d--) Sift(r,d,n); for(i=1;i temp=r[1]; r[1]=r[n-i+1]; r[n-i+1]=temp; Sift(r,1,n-i); } } //归并排序算法 void Merge(int r[],int r1[],int s,int m,int t) { int k=s,i=s,j=m+1; while(i<=m&&j<=t) { if(r[i] r1[k++]=r[j++]; } while(i<=m) r1[k++]=r[i++]; while(j<=t) r1[k++]=r[j++]; } void MergePass(int r[],int r1[],int n,int h) { int i=1; 第 5 页 共 5 页