排序方法比较 具体看下面要求 20C

对各种排序方法(直接插入排序、希尔排序、起泡排序、快速排序、直接选择排序、堆排序和归并排序)的时间性能进行比较。
1)基本要求:
(1) 设计并实现上述各种排序算法;
(2) 产生正序和逆序的初始排列分别调用上述排序算法,并比较时间性能;
(3) 产生随机的初始排列分别调用上述排序算法,并比较时间性能。

c

4个回答

qq_29594393
当作看不见 回复6666666翻: 这个各种算法都有了 ,完全符合要求 ,不知道还缺了什么
大约 3 年之前 回复
qq_34143673
天天晚睡的人 江湖救急的有没有
大约 3 年之前 回复

#include
#include
#include
#define MAXSIZE 30
#define Keytype int
struct enode{
char flag;
Keytype key;
};
typedef struct enode Elemtype;
typedef struct node Sqntable;
struct node{
Elemtype elem[MAXSIZE+1];
int last;
};
void Quick_Sort_T(Sqntable &r);
void Create_Sqn(Sqntable &r)
{
int rand();
r.last=8;
for(int i=1;i<=r.last;i++)
r.elem[i].key=rand()%100+3;
for(int j=1;j<=r.last;j++)
r.elem[j].flag='A'-1+j;
}
int Order_Search(Sqntable r,Keytype key) //顺序查找,找到返回位置值,没有找到返回0
{
int i=r.last;
r.elem[0].key=key;
while(key!=r.elem[i].key)
i--;
return i;
}
int Binary_Search(Sqntable r,Keytype key) //折半查找非递归算法,找到返回位置值,没有找到返回0
{
Quick_Sort_T(r);
int l,h,mid;
l=1;
h=r.last;
while(l<=h)
{
mid=(l+h)/2;
if(key h=mid-1;
else if(key>r.elem[mid].key)
l=mid+1;
else
return mid;
}
return 0;
}
int Dinary_Recursion_Search(Sqntable r,int m,int n,Keytype key)

{

int mid;

int l=m,h=n;

mid=(l+h)/2;

if(r.elem[mid].key==key)

{

return mid;

}

if(mid==h||mid==0)

{

return 0;

}

if(r.elem[mid].key>key)

{

if(r.elem[h].key==key)

{

return h;

}

h=mid;

return Dinary_Recursion_Search(r,l,h,key);

}

else

{ if(h-l==1)

{

return 0;

}

    l=mid;    
    return Dinary_Recursion_Search(r,l,h,key);    
}    

}

int Dinary_Recursion(Sqntable r,Keytype key) //折半查找递归算法,找到返回位置值,没有找到返回0
{
return Dinary_Recursion_Search(r,1,r.last,key);
}
void Swap(Elemtype l,Elemtype &m,Elemtype &n)
{
l=m;
m=n;
n=l;
}
void D_InsertSort(Sqntable &r) //直接插入排序
{
int i,j;
for(i=2;i<=r.last;i++)
if(r.elem[i].key {
r.elem[0]=r.elem[i];
for(j=i-1;r.elem[0].key {
r.elem[j+1]=r.elem[j];
}
r.elem[j+1]=r.elem[0];
}
}
void Select_Sort(Sqntable &r) //直接选择排序
{
int k;
for(int i=0;i {
k=i;
for(int j=k+1;j if(r.elem[k].key>r.elem[j].key)
k=j;
if(k!=i)
Swap(r.elem[0],r.elem[i],r.elem[k]);
}
}

void Foam_Sort(Sqntable &r) //起泡排序
{
int flag;
for(int i=1; i<=r.last-1; i++)

{
flag=0;

for(int j=r.last-1;j>=i; j--)
if(r.elem[j+1].key {
Swap(r.elem[0],r.elem[j+1],r.elem[j]);
flag=1;
}
if(flag==0)
break;
}
}
int Quick_S(Sqntable &r,int l,int h)
{
int i,j;
i=l;
j=h;
r.elem[0]=r.elem[i];
while(i {
while(i=r.elem[0].key)
j--;
r.elem[i]=r.elem[j];

while(i<j&&r.elem[i].key<=r.elem[0].key)
i++;
r.elem[j]=r.elem[i];
}
r.elem[i]=r.elem[0];
return i;
}
void Quick_Sort(Sqntable &r,int l,int h)
{
int i;
if(l<h)
{
i=Quick_S(r,l,h);
Quick_Sort(r,l,i-1);
Quick_Sort(r,i+1,h);
}
}
void Quick_Sort_T(Sqntable &r) //快速排序
{
int l,h;
l=1;
h=r.last;
Quick_Sort(r,l,h);
}
void Merge( Sqntable &r,Sqntable &t,int l,int m,int h )
{
int i,j,k;
i=l;
j=m+1;
k=l;
while(i<=m&&j<=h){
if(r.elem[i].key<r.elem[j].key)
t.elem[k++]=r.elem[i++];
else
t.elem[k++]=r.elem[j++];
}
while(i<=m)
t.elem[k++]=r.elem[i++];
while(j<=h)
t.elem[k++]=r.elem[j++];

for(int q=l; q<=h; q++)
    r.elem[q]=t.elem[q];

}
void Merge_sort(Sqntable &r,Sqntable &t,int l,int h)
{
if(l<h)
{
int mid;
mid=(l+h)/2;
Merge_sort(r,t,l,mid);
Merge_sort(r,t,mid+1,h);
Merge(r,t,l,mid,h);
}
}
void UnionSort(Sqntable &r) //合并排序
{
Sqntable t;
Merge_sort(r,t,1,r.last);
}
void Output(Sqntable r)
{
printf("表中的数据项为:\n");
printf("标记\t关键码\n");
for(int i=1;i<=r.last;i++)
printf("%c\t%d\n",r.elem[i].flag,r.elem[i].key);
}
void Select(Sqntable r,int i)
{
if(i)
{
printf("表中的数据项为:\n");
printf("标记\t关键码\n");
printf("%c\t%d\n",r.elem[i].flag,r.elem[i].key);
}
else
printf("*******此元素在表中没有找到!!!********\n");
}

int menu_select()
{
int cn;
printf("\t*************选择排序实验报告****************\n");
printf("\t***********> 1.顺序查找 <*******\n");
printf("\t***********> 2.二分查找(非递归) <*******\n");
printf("\t***********> 3.二分查找(递归) <*******\n");
printf("\t***********> 4,直接插入排序 <*******\n");
printf("\t***********> 5.直接选择排序 <*******\n");
printf("\t***********> 6.起泡排序 <*******\n");
printf("\t***********> 7.快速排序 <*******\n");
printf("\t***********> 8.合并排序 <*******\n");
printf("\t***********> 9.结束程序 <*******\n");
printf("\t*********************************************\n");
for( ; ;)
{
printf("你输入的操作为:");
scanf("%d",&cn);
if(cn9)
printf("\n输入错误!重选1—9:");
else
break;
}
return cn;
}
void Handle_menu(Sqntable &r)
{
system("color 3e");
for( ; ;)
{
int i;
switch(menu_select())
{
case 1:
printf("请输入要查找的元素关键码(直接查找):");
scanf("%d",&i);
i=Order_Search(r,i);
Select(r,i);
break;
case 2:
printf("请输入要查找的元素关键码(二分非递归):");
scanf("%d",&i);
i=Binary_Search(r,i);
Select(r,i);
break;
case 3:
printf("请输入要查找的元素关键码(二分递归):");
scanf("%d",&i);
i=Dinary_Recursion(r,i);
Select(r,i);
break;
case 4:
D_InsertSort(r);
Output(r);
printf("******>直接插入排序执行完毕!<*******\n");
break;
case 5:
Select_Sort(r);
Output(r);
printf("******>直接选择排序执行完毕!<*******\n");
break;
case 6:
Foam_Sort(r);
Output(r);
printf("******>起泡排序执行完毕!<*******\n");
break;
case 7:
Quick_Sort_T(r);
Output(r);
printf("******>快速排序执行完毕!<*******\n");
break;
case 8:
UnionSort(r);
Output(r);
printf("******>归并排序执行完毕!<*******\n");
break;
case 9:
return;
}

system("pause");
system("cls");
Output(r);
}
}
int main()
{
int i;
Sqntable r;
Create_Sqn(r);
Output(r);
Handle_menu(r);
return 0;
}


 #include<stdio.h>
#include<stdlib.h>
#include<windows.h>
#define MAXSIZE 30
#define Keytype int
struct enode{
    char flag;
    Keytype key;
};
typedef struct enode Elemtype;
typedef struct node Sqntable;
struct node{
    Elemtype elem[MAXSIZE+1];
    int last;
};
void Quick_Sort_T(Sqntable &r);
void Create_Sqn(Sqntable &r)
{
    int rand();
    r.last=8;
    for(int i=1;i<=r.last;i++)
        r.elem[i].key=rand()%100+3;
    for(int j=1;j<=r.last;j++)
        r.elem[j].flag='A'-1+j;
}
int Order_Search(Sqntable r,Keytype key)       //顺序查找,找到返回位置值,没有找到返回0
{
    int i=r.last;
    r.elem[0].key=key;
    while(key!=r.elem[i].key)
        i--;
    return i;
}
int Binary_Search(Sqntable r,Keytype key)       //折半查找非递归算法,找到返回位置值,没有找到返回0
{
    Quick_Sort_T(r);
    int l,h,mid;
    l=1;
    h=r.last;
    while(l<=h)
    {
        mid=(l+h)/2;
        if(key<r.elem[mid].key)
            h=mid-1;
        else if(key>r.elem[mid].key)
            l=mid+1;
        else
            return mid;
    }
    return 0;
}
int Dinary_Recursion_Search(Sqntable r,int m,int n,Keytype key)    
{    
    int mid;    
    int l=m,h=n;    
    mid=(l+h)/2;    
    if(r.elem[mid].key==key)    
    {    
        return mid;    
    }    
    if(mid==h||mid==0)    
    {    
        return 0;    
    }    
    if(r.elem[mid].key>key)    
    {    
        if(r.elem[h].key==key)  
        {  
            return h;  
        }  
        h=mid;    
        return Dinary_Recursion_Search(r,l,h,key);    
    }    
    else    
    {  if(h-l==1)  
        {  
            return 0;  
        }  

        l=mid;    
        return Dinary_Recursion_Search(r,l,h,key);    
    }    
}  
int Dinary_Recursion(Sqntable r,Keytype key)               //折半查找递归算法,找到返回位置值,没有找到返回0
{
    return Dinary_Recursion_Search(r,1,r.last,key);
}
void Swap(Elemtype l,Elemtype &m,Elemtype &n)
{
    l=m;
    m=n;
    n=l;
}
void D_InsertSort(Sqntable &r)        //直接插入排序
{
    int i,j;
    for(i=2;i<=r.last;i++)
        if(r.elem[i].key<r.elem[i-1].key)
        {
            r.elem[0]=r.elem[i];
            for(j=i-1;r.elem[0].key<r.elem[j].key;j--)
            {
                r.elem[j+1]=r.elem[j];
            }
            r.elem[j+1]=r.elem[0];
        }
}
void Select_Sort(Sqntable &r)        //直接选择排序
{
    int k;
    for(int i=0;i<=r.last-1;i++)
    {
        k=i;
        for(int j=k+1;j<=r.last;j++)
            if(r.elem[k].key>r.elem[j].key)
                k=j;
            if(k!=i)
                Swap(r.elem[0],r.elem[i],r.elem[k]);
    }
}

void Foam_Sort(Sqntable &r)          //起泡排序
{ 
     int flag; 
     for(int i=1; i<=r.last-1; i++)  
     {
        flag=0;                     
        for(int j=r.last-1;j>=i; j--)
        if(r.elem[j+1].key<r.elem[j].key)    
        {
          Swap(r.elem[0],r.elem[j+1],r.elem[j]);
          flag=1; 
        }
        if(flag==0)                  
           break;     
    }
}
int Quick_S(Sqntable &r,int l,int h)
{
    int i,j;
    i=l;
    j=h;
    r.elem[0]=r.elem[i];
    while(i<j)
    {
        while(i<j&&r.elem[j].key>=r.elem[0].key)
            j--;
        r.elem[i]=r.elem[j];        
        while(i<j&&r.elem[i].key<=r.elem[0].key)
            i++;
        r.elem[j]=r.elem[i];
    }
    r.elem[i]=r.elem[0];
    return i;
}
void Quick_Sort(Sqntable &r,int l,int h)
{
    int i;
    if(l<h)
    {
        i=Quick_S(r,l,h);
        Quick_Sort(r,l,i-1);
        Quick_Sort(r,i+1,h);
    }
}
void Quick_Sort_T(Sqntable &r)      //快速排序
{
    int l,h;
    l=1;
    h=r.last;
    Quick_Sort(r,l,h);
}
void Merge( Sqntable &r,Sqntable &t,int l,int m,int h )
{
    int i,j,k;
    i=l;
    j=m+1;
    k=l;
    while(i<=m&&j<=h){
        if(r.elem[i].key<r.elem[j].key)
            t.elem[k++]=r.elem[i++];
        else
            t.elem[k++]=r.elem[j++];
    }
    while(i<=m)
        t.elem[k++]=r.elem[i++];
    while(j<=h)
        t.elem[k++]=r.elem[j++];

    for(int q=l; q<=h; q++)
        r.elem[q]=t.elem[q];
}
void Merge_sort(Sqntable &r,Sqntable &t,int l,int h)
{
    if(l<h)
    {
        int mid;
        mid=(l+h)/2;
        Merge_sort(r,t,l,mid);
        Merge_sort(r,t,mid+1,h);
        Merge(r,t,l,mid,h);
    }
}
void UnionSort(Sqntable &r)              //合并排序
{
    Sqntable t;
    Merge_sort(r,t,1,r.last);
}
void Output(Sqntable r)
{
    printf("表中的数据项为:\n");
    printf("标记\t关键码\n");
    for(int i=1;i<=r.last;i++)
        printf("%c\t%d\n",r.elem[i].flag,r.elem[i].key);
}
void Select(Sqntable r,int i)
{
    if(i)
    {
        printf("表中的数据项为:\n");
        printf("标记\t关键码\n");
        printf("%c\t%d\n",r.elem[i].flag,r.elem[i].key);
    }
    else
        printf("*******此元素在表中没有找到!!!********\n");
}

int menu_select()
{
    int cn;
    printf("\t*************选择排序实验报告****************\n");
    printf("\t***********>    1.顺序查找           <*******\n");
    printf("\t***********>    2.二分查找(非递归) <*******\n");
    printf("\t***********>    3.二分查找(递归)   <*******\n");
    printf("\t***********>    4,直接插入排序       <*******\n");
    printf("\t***********>    5.直接选择排序       <*******\n");
    printf("\t***********>    6.起泡排序           <*******\n");
    printf("\t***********>    7.快速排序           <*******\n");
    printf("\t***********>    8.合并排序           <*******\n");
    printf("\t***********>    9.结束程序           <*******\n");
    printf("\t*********************************************\n");
    for( ; ;)
    {
        printf("你输入的操作为:");
        scanf("%d",&cn);
        if(cn<1||cn>9)
            printf("\n输入错误!重选1—9:");
        else
            break;
    }
    return cn;
}
void Handle_menu(Sqntable &r)
{
    system("color 3e");
    for( ; ;)
    {
        int i;
        switch(menu_select())
        {
        case 1:
            printf("请输入要查找的元素关键码(直接查找):");
            scanf("%d",&i);
            i=Order_Search(r,i);
            Select(r,i);
            break;
        case 2:
            printf("请输入要查找的元素关键码(二分非递归):");
            scanf("%d",&i);
            i=Binary_Search(r,i);
            Select(r,i);
            break;
        case 3:
            printf("请输入要查找的元素关键码(二分递归):");
            scanf("%d",&i);
            i=Dinary_Recursion(r,i);
            Select(r,i);
            break;
        case 4:
            D_InsertSort(r);
            Output(r);
            printf("******>直接插入排序执行完毕!<*******\n");
            break;
        case 5:
            Select_Sort(r);
            Output(r);
            printf("******>直接选择排序执行完毕!<*******\n");
            break;
        case 6:
            Foam_Sort(r);
            Output(r);
            printf("******>起泡排序执行完毕!<*******\n");
            break;
        case 7:
            Quick_Sort_T(r);
            Output(r);
            printf("******>快速排序执行完毕!<*******\n");
            break;
        case 8:
            UnionSort(r);
            Output(r);
            printf("******>归并排序执行完毕!<*******\n");
            break;
        case 9:
            return;
        }   
        system("pause");
        system("cls");
        Output(r);
    }
}
int main()
{
    int i;
    Sqntable r;
    Create_Sqn(r);
    Output(r);
    Handle_menu(r);
    return 0;
}

算法代码自己搜去,都是现成的,效率数据结构上都会讲

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问