数据结构课程设计_排序算法比较【完整版】

2、系统显示出随机产生的随机数。

用户选择排序方式，比如选择1.直接插入排序

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

3、系统将随机数排序后整齐的显示出来。

4、用户可以选择继续排序或者退出系统。

七、程序源代码

/********************************************************************************************** 第六题：排序算法比较

设计要求：利用随机函数产生N个随机整数（N = 500，1000，1500，2000，2500，…,30000），

第 7 页 共 20 页

利用直接插入排序、折半插入排序，起泡排序、快速排序、||选择排序、堆排序，基数排序七种排序方法

（可添加其它排序方法）进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的时间（统计

为图表坐标形式）。

************************************************************************************************/ #include \#include \

#include \计时

#define ERROR 0 #define OK 1

#define OVERFLOW -2

#define MAXSIZE //用户自己规定排序的数字的长度

typedef int Status;

typedef struct {

int *r; // r[0]闲置

int length; //顺序表的总长度 }Sqlist;

//构造一个空线性表

Status InitSqlist(Sqlist &L) { L.r=(int *)malloc(MAXSIZE*sizeof(int)); //分配存储空间 if(!L.r) { printf(\存储分配失败！\ exit(0); } //存储分配失败 L.length=0;//初始长度为0 return OK; }

//输入随机数并显示在界面上

Status ScanfSqlist(int &N,Sqlist &L) { int i; printf(\请输入要排序的元素个数N: \ scanf(\ for(i=1;i<=N;i++) L.r[i]=rand(); //随机产生样本整数

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

printf(\ printf(\ 随机产生了%d个随机数，它们是：\\n\ for(i=1;i<=N;i++) { printf(\ \ } printf(\ L.length=N; //存储线性表的长度 return OK; }

//输出排序之后的数据

Status PrintfSqlist(int N,Sqlist L) { int i; printf(\数据个数：\输出数据个数 printf(\ printf(\排序后的数据：(从左向右依次增大)\\n\输出数据 for(i=1;i<=N;i++) printf(\ \ printf(\ return OK; }

//*************************************************************** // 直接插入排序

//*************************************************************** Status InsertSort(Sqlist &L) //参考书P265算法10.1 { int i,j; if(L.length==0) { printf(\要排序的数据为空！\ return ERROR; } for(i=2;i<=L.length;i++) { if(L.r[i]

第 9 页 共 20 页

for(j=i-2;L.r[0]

//*************************************************************** // 折半插入排序

//*************************************************************** Status BInsertSort(Sqlist &L) //参考书P267算法10.2 { int i,j,mid,low,high; if(L.length==0) { printf(\要排序的数据为空！\ return ERROR; } for(i=2;i<=L.length;i++) { L.r[0]=L.r[i]; //将L.r[i]暂存在L.r[0] low=1; high=i-1; while(low<=high) //在r[low..high]中折半查找有序插入的位置 { mid=(low+high)/2; if(L.r[0]=high+1;j--) //插入点后的数据后移 { L.r[j+1]=L.r[j]; } L.r[high+1]=L.r[0]; //将数据插入