数据结构课程设计 - 排序算法比较[完整版]

数据结构课程设计——排序算法比较

课程设计报告

数据结构课程设计题目：各种排序

学生姓名：高扬

专 业：网络工程 班 级：10211302 学 号：1021130221 指导教师：姜林 王志波

2012年6 月27 第 1 页 共 15 页

日

数据结构课程设计——排序算法比较

目 录

排序算法比较

一、程序要求分析

二、程序主要功能

三、程序运行平台

四、程序数据结构

五、算法及时间复杂度

六、程序源代码

七、自我总结

第 2 页 共 15 页

数据结构课程设计——排序算法比较

各 种 排 序

一、需求分析

任务：用程序实现插入法排序、起泡法、选择法、快速法、合并法排序；

输入的数据形式为任何一个正整数，大小不限。 输出的形式：数字大小逐个递增的数列。

要求给出多组不同元素个数的输入数据，并用列表打印出每种排序下的各趟排序结果。每个排序法结束时应打印出其元素比较的次数和交换的次数。此程序需将结果用列表打印，一定要将其打印结果排列好。

二、程序的主要功能

1.用户输入任意个数，产生相应数量的随机数

2.用户可以自己选择排序方式（直接插入排序，冒泡排序、快速排序、选择排序、二路归并排序五种排序方法）的一种

3.程序给出原始数据、排序后从小到大的数据，并给出排序所用的时间，比较的总次数和交换的总次数。

三、程序运行平台

Visual C++ 6.0版本

四、数据结构

1.类： NuovSort{ public: void Myface(); void choose(); void insertsort(int R[],int n); //直接插入排序法 void Bubblesort(int R[],int n); //冒泡排序算法实现 void quicksort(int R[],int left,int right); //快速排序算法实现 void selectsort(int R[],int n); //直接选择排序算法实现

第 3 页 共 15 页

数据结构课程设计——排序算法比较

void merge(int R[],int A[],int s,int m,int t);//二路归并排序算法实现 void mergepass(int R[],int A[],int n,int c); void mergesort(int R[],int n); };

2.主界面：

Myface() //界面 { cout<<\ -->各种排序算法实现<--\

cout<<\ cout<<\ 1.直接插入排序 #\ cout<<\ 2.冒泡排序 #\ cout<<\ 3.快速排序 #\ cout<<\ 4.直接选择排序 #\ cout<<\ 5.二路归并排序 #\ cout<<\ cout<<\}

3.选择界面： choose() { int i,x,n,s,t; time_t t1,t2; double tt1,tt2,tt3,tt4,tt5; cout<<\欢迎您使用 高扬 的排序程序\ cout<<\请问，需要几个被排序数字？\ do{ cout<<\请输入个数(范围在 1~500 之间): \ cin>>n; } while((n<1)||(n>500)); int left=0,right=n-1; for(i=0;i

R[i]=rand()?8+1; //产生随机数

cout<<\被排序的数字随机产生如下：\ for(i=0;i

第 4 页 共 15 页