排序算法课程设计题1

第 1 页

数据结构的课程设计

课程名称： 课程设计题目： 姓名： 学院： 专业： 年级：

学号：

日期

年 月 日

第 1 页 共 1 页

第 2 页

排序算法课程设计题1

一、问题描述

排序算法是对一系列无序的数据进行排序，使之有序，根据算法思想及程序设计的不同，有多种排序算法：希尔排序、快速排序、堆排序、归并排序等。 二、几种排序算法的思想描述

? 希尔排序：该排序算法是在直接插入排序算法的基础上改进的,选取小于数据个数一个

整数d作为增量，将所有的数据分成d组，现在各组内进行直接插入排序，然后取第二个增量进行重复的分组和排序。

? 快速排序：是对冒泡排序算法对的一种改进，选择一个枢轴，其前面的数全都比其小，

后面的数据全都比其大。然后对两部分的数据进行相应的快速排序。 ? 堆排序：与完全二叉树相对应

? 归并排序：将两个有序的序列归并成为一个对应的有序的序列。 三、总体设计

各种排序算法的实现其实就是函数的实现，在一个头文件中实现，而在主函数中可以设置一个菜单函数来提供选择项，供用户选择选择项来选择使用哪个函数来进行排序，其中随机产生数据可以通过函数rand函数来实现，并且还涉及到对文件进行操作。

设计步骤

主函数void main()函数

调用rand()函数来产生1000个数 据，并同时存入磁盘文件中

从磁盘文件中读取数据到程序的数组中 序择函数进行排 通过菜单项选1.希尔排序 2.快速排序 3.堆排序 4.归并排序 将排序结果存入磁盘文件中

第 2 页 共 2 页

第 3 页

四、详细设计

? 模块一、函数头文件

#include #include #includ

? 模块二、主函数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 using namespace std; //希尔排序算法

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=temp) j--; if(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 页

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库排序算法课程设计题1在线全文阅读。