对各种排序方法（直接插入排序、希尔排序、起泡排序、快速排序、直接选择排序、堆排序和归并排序）的时间性能进行比较。
1）基本要求：
(1) 设计并实现上述各种排序算法；
(2) 产生正序和逆序的初始排列分别调用上述排序算法，并比较时间性能；
(3) 产生随机的初始排列分别调用上述排序算法，并比较时间性能。
算法代码自己搜去，都是现成的，效率数据结构上都会讲
http://blog.csdn.net/tanqian351/article/details/52061697?locationNum=4&fps=1
#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;
}