排序算法的比较

穷小疯 · 发表于 2019-12-23 22:24:46

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

利用随机函数产生 30000 个随机整数，利用插入排序、起泡排序、选择排序、快速排序、堆排序、归并排序等排序方法进行排序，并统计每一种排序上机所花费的时间和次数。

Status PrintfSqlist(int N,Sqlist L)
{
int i;
printf("数据个数：");//输出数据个数
printf("%d\n",L.length);
printf("排序后的数据：(从左向右依次增大)\n");//输出数据
for(i=1;i<=N;i++)
printf("%7.2d ",L.r[i]);
printf("\n");
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]<L.r[i-1]) //将L.r[i]插入有序子表
{
L.r[0]=L.r[i]; //复制为监视哨
L.r[i]=L.r[i-1];
for(j=i-2;L.r[0]<L.r[j];j--)
{
L.r[j+1]=L.r[j]; //记录后移
}
L.r[j+1]=L.r[0]; //插入到正确位置
}
}
return OK;
}
//***************************************************************
// 折半插入排序
//***************************************************************
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]<L.r[mid]) //插入点在低半区
{
high=mid-1;
}
else
{
low=mid+1; //插入点在高半区
}
}//while
for(j=i-1;j>=high+1;j--) //插入点后的数据后移
{
L.r[j+1]=L.r[j];
}
L.r[high+1]=L.r[0]; //将数据插入
}//for
return OK;
}
/********************************************************************************
希尔排序
*********************************************************************************/
//参考书P272算法10.4及10.5
/*Status ShellInsert(Sqlist &L,int dk) //希尔插入排序
{
int i,j; //前后位置的增量是dk
for(i=dk+1;i<=L.length;i++) //r[0]只是暂存单元，不是哨兵，
{
if(L.r[i]<L.r[i-dk]) //将L.r[i]插入有序增量子表
{
L.r[0]=L.r[i]; //暂存L.r[0]
for(j=i-dk;j>0 && L.r[0]<L.r[j];j-=dk)
{
L.r[j+dk]=L.r[j]; //记录后移,查找插入位置
}
L.r[j+dk]=L.r[0]; //插入
}
}
return OK;
}
Status ShellSort(Sqlist &L,int dlta[5],int t) //希尔排序
{
int i;
if(L.length==0)
{
printf("要排序的数据为空！");
return ERROR;
}
for(i=0;i<t;i++)
{
ShellInsert(L,dlta[i]); //一趟增量为dlta[k]的插入排序
}
return OK;
}
*/
//**************************************************************
// 起泡排序
//**************************************************************
Status BubbleSort(Sqlist &L)
{
int i,j,t;
if(L.length==0)
{
printf("要排序的数据为空！");
return ERROR;
}
for(i=1;i<=L.length-1;i++)
{
for(j=1;j<=L.length-i;j++)
{
if(L.r[j]>L.r[j+1]) //前面的数据>后面数据时
{
t=L.r[j+1];
L.r[j+1]=L.r[j];
L.r[j]=t; //将元素交换
}
}
}
return OK;
}
//****************************************************
// 快速排序
//****************************************************
int Partition(Sqlist &L, int low, int high) //交换顺序表中子表L.r[low..high]的记录，使得枢轴记录到位，并返回其所在位置，此时在它之前（后）的记录均不大于它
{
int pivotkey; //记录关键字
L.r[0]=L.r[low]; //用子表的第一个纪录作枢轴纪录
pivotkey=L.r[low]; //用枢轴纪录关键字
while (low<high)
{
while(low<high && L.r[high]>=pivotkey)
{
high--;
}
L.r[low]= L.r[high]; //将比枢轴记录小的记录移到低端
while(low<high && L.r[low]<=pivotkey)
{
low++;
}
L.r[high]=L.r[low]; //将比枢轴记录大的数移到高端
}
L.r[low]=L.r[0]; //枢轴记录到位
return low;
}//Partition函数
void Qsort (Sqlist &L,int low, int high)
{
int pivotloc;
if (low<high) //长度大于1，可以进行
{
pivotloc=Partition(L, low ,high);
Qsort(L,low,pivotloc-1); //对低子表递归排序，pivotloc是枢轴位置
Qsort(L,pivotloc+1,high); //对高子表递归排序
}
}//Qsort函数
Status QuickSort (Sqlist &L)
{
if(L.length==0)
{
printf("要排序的数据为空！");
return ERROR;
}
Qsort(L,1,L.length);
return OK;
}//QuickSort
//**********************************************
// 选择排序
//**********************************************
Status ChooseSort(Sqlist &L)
{
int i,j,k,t;
if(L.length==0)
{
printf("没有数据！");
return ERROR;
}
for(i=1;i<=L.length;i++) //排序的趟数
{
k=i;
for(j=i+1;j<=L.length;j++) //比较第i个元素以及其后的数据中最小的
{
if(L.r[j]<L.r[k])
k=j;
}
if(i!=j) //将最小数据赋值给L.r[i]
{
t=L.r[i];
L.r[i]=L.r[k];
L.r[k]=t;
}
}
return OK;
}
//****************************************
// 堆排序
//****************************************
Status HeapAdjust(Sqlist &L,int s,int m) //调整L.r[s]的关键字,使L.r[s~m]成大顶堆
{
int i;
L.r[0]=L.r[s];
for(i=2*s;i+1<=m;i*=2) //沿数据较大的孩子结点向下筛选
{
if(i<m && L.r[i]<L.r[i+1]) //i为数据较大的记录下标
i++;
if(L.r[0]>=L.r[i]) //L.r[0]插入在S位置上
break;
L.r[s]=L.r[i];
s=i;
}
L.r[s]=L.r[0]; //插入新数据
return OK;
}
Status HeapSort(Sqlist &L) //堆排序
{
int i,t;
if(L.length==0)
{
printf("没有数据！");
return ERROR;
}
for(i=L.length/2;i>0;i--)
HeapAdjust(L,i,L.length);
for(i=L.length;i>1;i--)
{
t=L.r[1]; //将堆顶记录和当前未经排序的子序列L.r[1..i]中最后一个记录互换
L.r[1]=L.r[i];
L.r[i]=t;
HeapAdjust(L,1,i-1); //将L.r[1..i-1]重新调整为大顶堆
}
return OK;
}
//**************************************************
// 基数排序
//**************************************************
typedef struct node{
int key;
node *next;
}RecType;
Status RadixSort(Sqlist L)
{
int t,i,j,k,d,n=1,m;
RecType *p,*s,*q,*head[10],*tail[10]; //定义各链队的首尾指针
for(i=1;i<=L.length;i++) //将顺序表转化为链表
{
s=(RecType*)malloc(sizeof(RecType));
s->key=L.r[i];
if(i==1) //当为第一个元素时
{
q=s;
p=s;
t++;
}
else
{
q->next=s; //将链表连接起来
q=s;
t++;
}
q->next=NULL;
}
d=1;
while(n>0) //将每个元素分配至各个链队
{
for(j=0;j<10;j++) //初始化各链队首、尾指针
{
head[j] = NULL;
tail[j] = NULL;
}
while(p!=NULL) //对于原链表中的每个结点循环
{
k=p->key/d;
k=k%10;
if(head[k]==NULL) //进行分配
{
head[k]=p;
tail[k]=p;
}
else
{
tail[k]->next=p;
tail[k]=p;
}
p=p->next; //取下一个待排序的元素
}
p=NULL; //用于收集第一个元素时的判断
for(j=0;j<10;j++) //对每一个链队循环，搜集每一个元素
{
if(head[j]!=NULL) //进行搜集
{
if(p==NULL)
{
p=head[j];
q=tail[j];
}
else
{
q->next=head[j];
q=tail[j];
}
}
}
q->next=NULL; //最后一个结点的next置为空
d=d*10;
n=0;
m=1;
while(m<=L.length) //判断当L中的元素都除d后是不是都为零了
{
if((L.r[m]/d)!=0)
{
n++;
m++;
}
else
m++;
}
}
i=1;
while(p!=NULL) //将链表转换为顺序表
{
L.r[i]=p->key;
i++;
p=p->next;
}
return OK;
}

复制代码

求助大佬运行结果就是算法名称排序次数运行时间这种格式请大佬帮帮忙

穷小疯 · 发表于 2019-12-25 17:42:31

Croper 发表于 2019-12-25 07:42
那么你为什么不把你不能运行的代码放上来，让大家帮你检查一下哪儿不对呢？

我重新发了一个帖子，能不能麻烦你去看看啊，我那里把代码发上去了

大尾巴 · 发表于 2019-12-25 13:39:29

各位大神啊，排序方法那么多，是不是要求每种排序法都要精通啊？？？？？

Croper · 发表于 2019-12-25 07:42:18

那么你为什么不把你不能运行的代码放上来，让大家帮你检查一下哪儿不对呢？

穷小疯 · 发表于 2019-12-24 08:46:30

Croper 发表于 2019-12-23 22:53
怎么看起来这么像作业呢？
作业就好好做，认真听了课的话这个肯定不难

这是我的课程设计，换了几种方法都不能运行，所以才来问的

Croper · 发表于 2019-12-23 22:53:47

怎么看起来这么像作业呢？
作业就好好做，认真听了课的话这个肯定不难

账号		自动登录	找回密码
密码			立即注册

排序算法的比较

马上注册，结交更多好友，享用更多功能^_^

回帖奖励 +30 鱼币

浏览过的版块