排序算法的比较
利用随机函数产生 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);
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<L.r)//将L.r插入有序子表
{
L.r=L.r;//复制为监视哨
L.r=L.r;
for(j=i-2;L.r<L.r;j--)
{
L.r=L.r;//记录后移
}
L.r=L.r;//插入到正确位置
}
}
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=L.r;//将L.r暂存在L.r
low=1;
high=i-1;
while(low<=high)//在r中折半查找有序插入的位置
{
mid=(low+high)/2;
if(L.r<L.r)//插入点在低半区
{
high=mid-1;
}
else
{
low=mid+1;//插入点在高半区
}
}//while
for(j=i-1;j>=high+1;j--)//插入点后的数据后移
{
L.r=L.r;
}
L.r=L.r; //将数据插入
}//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只是暂存单元，不是哨兵，
{
if(L.r<L.r) //将L.r插入有序增量子表
{
L.r=L.r; //暂存L.r
for(j=i-dk;j>0 && L.r<L.r;j-=dk)
{
L.r=L.r; //记录后移,查找插入位置
}
L.r=L.r; //插入
}
}
return OK;
}
Status ShellSort(Sqlist &L,int dlta,int t) //希尔排序
{
int i;
if(L.length==0)
{
printf("要排序的数据为空！");
return ERROR;
}
for(i=0;i<t;i++)
{
ShellInsert(L,dlta); //一趟增量为dlta的插入排序
}
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>L.r) //前面的数据>后面数据时
{
t=L.r;
L.r=L.r;
L.r=t;//将元素交换
}
}
}
return OK;
}
//****************************************************
// 快速排序
//****************************************************
int Partition(Sqlist &L, int low, int high) //交换顺序表中子表L.r的记录，使得枢轴记录到位，并返回其所在位置，此时在它之前（后）的记录均不大于它
{
int pivotkey;//记录关键字
L.r=L.r;//用子表的第一个纪录作枢轴纪录
pivotkey=L.r;//用枢轴纪录关键字
while (low<high)
{
while(low<high && L.r>=pivotkey)
{
high--;
}
L.r= L.r;//将比枢轴记录小的记录移到低端
while(low<high && L.r<=pivotkey)
{
low++;
}
L.r=L.r;//将比枢轴记录大的数移到高端
}
L.r=L.r;//枢轴记录到位
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函数
StatusQuickSort (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<L.r)
k=j;
}
if(i!=j)//将最小数据赋值给L.r
{
t=L.r;
L.r=L.r;
L.r=t;
}
}
return OK;
}
//****************************************
// 堆排序
//****************************************
Status HeapAdjust(Sqlist &L,int s,int m)//调整L.r的关键字,使L.r成大顶堆
{
int i;
L.r=L.r;
for(i=2*s;i+1<=m;i*=2)//沿数据较大的孩子结点向下筛选
{
if(i<m && L.r<L.r)//i为数据较大的记录下标
i++;
if(L.r>=L.r)//L.r插入在S位置上
break;
L.r=L.r;
s=i;
}
L.r=L.r; //插入新数据
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;//将堆顶记录和当前未经排序的子序列L.r中最后一个记录互换
L.r=L.r;
L.r=t;
HeapAdjust(L,1,i-1);//将L.r重新调整为大顶堆
}
return OK;
}
//**************************************************
// 基数排序
//**************************************************
typedef struct node{
intkey;
node *next;
}RecType;
Status RadixSort(Sqlist L)
{
int t,i,j,k,d,n=1,m;
RecType *p,*s,*q,*head,*tail;//定义各链队的首尾指针
for(i=1;i<=L.length;i++)//将顺序表转化为链表
{
s=(RecType*)malloc(sizeof(RecType));
s->key=L.r;
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 = NULL;
tail = NULL;
}
while(p!=NULL)//对于原链表中的每个结点循环
{
k=p->key/d;
k=k%10;
if(head==NULL)//进行分配
{
head=p;
tail=p;
}
else
{
tail->next=p;
tail=p;
}
p=p->next;//取下一个待排序的元素
}
p=NULL;//用于收集第一个元素时的判断
for(j=0;j<10;j++)//对每一个链队循环， 搜集每一个元素
{
if(head!=NULL)//进行搜集
{
if(p==NULL)
{
p=head;
q=tail;
}
else
{
q->next=head;
q=tail;
}
}
}
q->next=NULL;//最后一个结点的next置为空
d=d*10;
n=0;
m=1;
while(m<=L.length)//判断当L中的元素都除d后是不是都为零了
{
if((L.r/d)!=0)
{
n++;
m++;
}
else
m++;
}
}
i=1;
while(p!=NULL) //将链表转换为顺序表
{
L.r=p->key;
i++;
p=p->next;
}
return OK;
}
求助大佬运行结果就是 算法名称 排序次数 运行时间这种格式请大佬帮帮忙 怎么看起来这么像作业呢？
作业就好好做，认真听了课的话这个肯定不难 Croper 发表于 2019-12-23 22:53
怎么看起来这么像作业呢？
作业就好好做，认真听了课的话这个肯定不难
这是我的课程设计，换了几种方法都不能运行，所以才来问的 那么你为什么不把你不能运行的代码放上来，让大家帮你检查一下哪儿不对呢？ 各位大神啊，排序方法那么多，是不是要求每种排序法都要精通啊？？？？？ Croper 发表于 2019-12-25 07:42
那么你为什么不把你不能运行的代码放上来，让大家帮你检查一下哪儿不对呢？
我重新发了一个帖子，能不能麻烦你去看看啊，我那里把代码发上去了
页:
[1]