Question

求一个程序把几种排序算法包含在内，有一个直观的比较。主要是能运行的完整代码。。C语言,C++都可以

Answer 1

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<string.h>
#include<windows.h>
#pragma comment(lib,"winmm.lib")
#define TRUE 1
#define FALSE 0
#define SNUM 7
int comp[SNUM]={0},move[SNUM]={0};
void Insert(int a[],int n){//直接插入排序
int i,j,temp;
for(i=1;i<n;i++){
comp[0]++;
if(a[i]<a[i-1]){
temp=a[i];move[0]++;
for(j=i-1;j>=0&&temp<a[j];j--){
a[j+1]=a[j];move[0]++;comp[0]++;
}
a[j+1]=temp;move[0]++;
}
}
}
void Shell(int a[],int n){//希尔排序
int i,j,temp,dk;
for(dk=n/2;dk>0;dk=dk/2)
for(i=dk;i<n;i++){
comp[1]++;
if(a[i]<a[i-dk]){
temp=a[i];move[1]++;
for(j=i-dk;j>=0&&temp<a[j];j-=dk)
{a[j+dk]=a[j];move[1]++;comp[0]++;}
a[j+dk]=temp;move[1]++;
}
}
}
void Bubble(int a[],int n){ //冒泡排序
int temp,i,j;
int NOSWAP;
for(i=n-1;i>0;--i){
NOSWAP=TRUE;
for(j=0;j<i;j++){
comp[2]++;
if(a[j]>a[j+1]){
temp=a[j];a[j]=a[j+1];
a[j+1]=temp;NOSWAP=FALSE;
move[2]+=3;
}
}
if(NOSWAP)break;
}
}
void Quick(int a[],int low,int high){ //快速排序
int temp,L=low,H=high;
if(low<high){
temp=a[low];move[3]++; //用区间的第1个记录作为基准
while(low<high){
while(low<high&&a[high]>=temp)
{high--;comp[3]++;}
a[low]=a[high];move[3]++;
while(low<high&&a[low]<=temp)
{low++;comp[3]++;}
a[high]=a[low];move[3]++;
}
a[low]=temp; move[3]++; //low的值相当于pivotkey
Quick(a,L,low-1);//对左区间递归排序
Quick(a,low+1,H);//对右区间递归排序
}
}
void SelectSort(int a[],int n){ //简单选择排序
int i,j,k,tmp;
for(i=0;i<n-1;i++){
k=i;
for(j=i+1;j<n;j++){
comp[4]++;
if(a[j]<a[k])k=j;
}
if(i!=k){
tmp=a[i];a[i]=a[k];
a[k]=tmp;move[4]+=3;
}
}
}
void HeapAdjust(int a[],int s,int m){ //使H.r[s..m]成为一个大顶堆
int j,tmp;
tmp=a[s]; move[5]++;
for(j=2*s+1;j<=m;j*=2){ //j为s的左孩子，所以j=2*s+1
comp[5]++;
if(j<m&&a[j]<a[j+1])++j;
if(tmp>=a[j]) break;
a[s]=a[j];move[5]++;
s=j;
}
a[s]=tmp;
}
void HeapSort(int a[],int n){ //堆排序
int i,tmp;
for(i=n/2-1;i>=0;--i)
//从最后一个元素的下标j(=n-1)=2*i+1开始，所以i=n/2-1
HeapAdjust(a,i,n-1); //将初始待排记录建成一个大顶堆
for(i=n-1;i>0;--i){
tmp=a[i];a[i]=a[0];a[0]=tmp;
move[5]+=3;
HeapAdjust(a,0,i-1);
}
}
void Merge(int a[],int low,int m,int high)
{//将两个有序的子序列a[low..m)和a[m+1..high]归并成一个
//有序的子序列a[low..high]
int *b; //b为辅助数组基址
b=(int*)malloc((high-low+1)*sizeof(int));
for(int i=low,j=m+1,k=0;i<=m&&j<=high;++k){
//两子序列均非空时取其小者输出到b[k]上
if(a[j]<a[i])b[k]=a[j++];
else b[k]=a[i++];
move[6]++;comp[6]++;
}
while(i<=m) //若第1个子序列非空，则复制剩余记录到b中
{b[k++]=a[i++];move[6]++;}
while(j<=high) //若第2个子序列非空，则复制剩余记录到b中
{b[k++]=a[j++];move[6]++;}
for(k=0,i=low;i<=high;k++,i++,move[6]++)
a[i]=b[k];//归并完成后将结果复制回a[low..high]
free(b);
}
void MergeSort(int a[],int low,int high){
//用分治法对a[low..high]进行二路归并排序
int mid;
if(low<high){//区间长度大于1
mid=(low+high)/2;//分解
MergeSort(a,low,mid);//递归地对a[low..mid]排序
MergeSort(a,mid+1,high); //递归地对a[mid+1..high]排序
Merge(a,low,mid,high);//组合，将两个有序区归并为一个有序区
}
}
_int64 Runtime(int *b,int n,char TYPE){
int *a;
LARGE_INTEGER ft;
_int64 begin_t,end_t;
a=(int*)malloc(n*sizeof(int));
if(!a)exit(0);
for(int i=0;i<n;i++)a[i]=b[i];
QueryPerformanceCounter(&ft);
begin_t=ft.QuadPart;
switch(TYPE){
case'I':Insert(a,n);break;
case'S':Shell(a,n);break;
case'B':Bubble(a,n);break;
case'Q':Quick(a,0,n-1);break;
case'J':SelectSort(a,n);break;
case'H':HeapSort(a,n);break;
case'2':MergeSort(a,0,n-1);
}
QueryPerformanceCounter(&ft);
end_t=ft.QuadPart;
free(a);
return end_t-begin_t;
}
void Disp(int n,double e[]){
static num;
int s[SNUM];
for(int i=0;i<SNUM;i++)s[i]=comp[i]+move[i];
printf(" 第%d次测试结果 \n",num++);
printf("-----------------------------------------------------------\n");
printf("| 排序算法 | 比较次数 | 移动次数 | 总次数 | 耗费时间 | \n");
printf("-----------------------------------------------------------\n");
printf("|直接插入排序| %10u %10u %10u %6.2fms\n",comp[0],move[0],s[0],e[0]);
printf("| 希尔排序 | %10u %10u %10u %6.2fms\n",comp[1],move[1],s[1],e[1]);
printf("| 起泡排序 | %10u %10u %10u %6.2fms\n",comp[2],move[2],s[2],e[2]);
printf("| 快速排序 | %10u %10u %10u %6.2fms\n",comp[3],move[3],s[3],e[3]);
printf("|简单选择排序| %10u %10u %10u %6.2fms\n",comp[4],move[4],s[4],e[4]);
printf("| 堆排序 | %10u %10u %10u %6.2fms\n",comp[5],move[5],s[5],e[5]);
printf("|2-路归并排序| %10u %10u %10u %6.2fms\n",comp[6],move[6],s[6],e[6]);
printf("-----------------------------------------------------------\n");
}
void main()
{
int i,n,*b;
LARGE_INTEGER ft;
_int64 k,j,tmp,zhp;
double sum,e[SNUM]={0};
srand(time(NULL));
QueryPerformanceFrequency(&ft);
zhp=ft.QuadPart;
do{
QueryPerformanceCounter(&ft);
k=ft.QuadPart;
printf("输入待排序元素个数(输入0结束)：");
scanf("%d",&n);
b=(int*)malloc(n*sizeof(int));
for(i=0;i<n;i++)b[i]=rand()*rand()%100000;
tmp=Runtime(b,n,'I');
e[0]=(double)tmp/(double)zhp*1000;
tmp=Runtime(b,n,'S');
e[1]=(double)tmp/(double)zhp*1000;
tmp=Runtime(b,n,'B');
e[2]=(double)tmp/(double)zhp*1000;
tmp=Runtime(b,n,'Q');
e[3]=(double)tmp/(double)zhp*1000;
tmp=Runtime(b,n,'J');
e[4]=(double)tmp/(double)zhp*1000;
tmp=Runtime(b,n,'H');
e[5]=(double)tmp/(double)zhp*1000;
tmp=Runtime(b,n,'2');
e[6]=(double)tmp/(double)zhp*1000;
if(n>0)Disp(n,e);
QueryPerformanceCounter(&ft);
j=ft.QuadPart;
sum=(double)(j-k)/(double)zhp*1000;
printf("\n程序运行总时间为：%1.2fms\n",sum);
for(i=0;i<SNUM;i++)comp[i]=move[i]=0;//初始化
free(b);
}while(n>0);
system("pause");
}

Answer 2

百度一下 rosetta code 这个网站，上面有高手写的各种算法的详尽版本。

Answer 3

自己用c写的，你参考包含6种排序，运行正确，包含每一步排序的变化，不懂可以再留言，希望采纳！！

#include <stdio.h>
#include <stdlib.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define MAXSIZE 20

typedef struct shaobing
{
int key;
}shaobing;
typedef struct
{
shaobing r[MAXSIZE+1];//r[0]用作哨兵或闲置
int *elem;
int length;
int listsize;
}SqList;

void CreateList (SqList &L)
{
L.elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));
if(!L.r)
return;
L.listsize=LIST_INIT_SIZE;
printf("建立一个顺序表:\n请输入表中的长度\n");
scanf("%d",&L.length);
printf("请输入表中的元素\n");
for(int i=1;i<=L.length;i++)
scanf("%d",&L.r[i]);

}//CreateList

void Insertsort1(SqList &L)
{//对顺序表进行直接插入排序
printf("直接插入排序结果:\n");
for(int i=2;i<=L.length;i++)
{
if(L.r[i].key<L.r[i-1].key)
{
L.r[0].key=L.r[i].key;
L.r[i].key=L.r[i-1].key;
for(int j=i-2;L.r[0].key<L.r[j].key;j--)
L.r[j+1].key=L.r[j].key;
L.r[j+1].key=L.r[0].key;
}
printf("第%d趟:\n",i-1);
for(int n=1;n<=L.length;n++)
printf("%5d",L.r[n].key);
printf("\n");
}

}

void Insertsort2(SqList &L)
{//对顺序表进行折半插入排序
int low,high,m,i,j;
for(i=2;i<=L.length;i++)
{
L.r[0].key=L.r[i].key;
low=1;
high=i-1;
while(low<=high)
{
m=(low+high)/2;
if(L.r[0].key<L.r[m].key)
high=m-1;
else
low=m+1;
}
for(j=i-1;j>=high+1;j--)
L.r[j+1].key=L.r[j].key;
L.r[high+1].key=L.r[0].key;
printf("第%d趟:\n",i-1);
for(int n=1;n<=L.length;n++)
printf("%5d",L.r[n].key);
printf("\n");

}
}

void Insertsort3(SqList &L)
{//冒泡排序
int i,j;
int flag=1;
for(i=1;i<L.length&&flag;i++)
{
flag=0;
for(j=1;j<=L.length-i;j++)
if(L.r[j].key>=L.r[j+1].key)
{
L.r[0].key=L.r[j].key;
L.r[j].key=L.r[j+1].key;
L.r[j+1].key=L.r[0].key;
}
flag=1;
printf("第%d趟:\n",i);
for(int n=1;n<=L.length;n++)
printf("%5d",L.r[n].key);
printf("\n");

}
}

int Partition(SqList &L,int low,int high)
{//快速排序
L.r[0].key=L.r[low].key;
while(low<high)

{
while(low<high&&L.r[high].key>=L.r[low].key)
high--;
if(low<high)
{
L.r[low].key=L.r[high].key;
low++;
}
while(low<high&&L.r[low].key<=L.r[0].key)
low++;
if(low<high)
{
L.r[high].key=L.r[low].key;
high--;
}
}
L.r[low].key=L.r[0].key;
return low;
}
void Insertsort(SqList &L,int low,int high)
{//快速排序递归算法
if(low<high)
{
int a;
a=Partition(L,low,high);
Insertsort(L,low,a-1);
Insertsort(L,a+1,high);
}
}

void Insertsort4(SqList &L)
{//快速排序
for(int i=1;i<=L.length;i++)
{
Insertsort(L,i,L.length-1);
printf("第%d趟:\n",i);
for(int n=1;n<=L.length;n++)
printf("%5d",L.r[n].key);
printf("\n");
}

}
int SelectMinKey(SqList L,int i)
{//选择此时顺序表中最小的元素
int min=32767,j;
for(;i<=L.length;i++)
if(L.r[i].key<min)
{
min=L.r[i].key;
j=i;
}
return j;
}
void Insertsort5(SqList &L)
{//对顺序表进行简单选择排序
int j,i,a=1;
for( i=1;i<=L.length;i++)
{
j=SelectMinKey(L,i);
if(i!=j)
{
L.r[0].key=L.r[i].key;
L.r[i].key=L.r[j].key;
L.r[j].key=L.r[0].key;
}
printf("第%d趟:\n",a++);
for(int h=1;h<=L.length;h++)
printf("%5d",L.r[h].key);
printf("\n");
}
/*printf("排序结果为：\n");
for(i=1;i<=L.length;i++)
printf("%5d",L.r[i].key);*/
}
void HeapAdjust(SqList &L,int s,int m)
{//调整L.r[s...m]成为一个大顶堆
int j;
L.r[0].key=L.r[s].key ;
for(j=2*s;j<=m;j*=2)
{
if(j<m&&L.r[j].key <L.r[j+1].key )
j++;
if(L.r[0].key>=L.r[j].key )
break;
L.r[s].key =L.r[j].key ;
s=j;
}
L.r[s].key =L.r[0].key;
}
void Insertsort6(SqList &L)
{//堆排序
int i,a=1,h;
for(i=L.length/2;i>0;i--)
HeapAdjust(L,i,L.length);
for(i=L.length;i>1;i--,a++)
{
L.r[0].key=L.r[1].key ;
L.r[1].key=L.r[i].key ;
L.r[i].key=L.r[0].key;
printf("第%d趟:\n",a);
for(h=1;h<=L.length;h++)
printf("%5d",L.r[h].key);
printf("\n");
HeapAdjust(L,1,i-1);
}
}
void menu(SqList &L,int e)
{//菜单：输入1---直接插入排序\n输入2---折半插入排序\n输入3---冒泡排序\n输入4---快速排序\n输入5---简单选择排序\n输入6---堆排序
switch(e)
{
case 1: CreateList (L);Insertsort1(L);break;
case 2: CreateList (L);Insertsort2(L);break;
case 3: CreateList (L);Insertsort3(L);break;
case 4: CreateList (L);Insertsort4(L);break;
case 5: CreateList (L);Insertsort5(L);break;
case 6: CreateList (L);Insertsort6(L);break;
default: printf("输入数据错误:\n");
}
}

void main()
{
SqList L;
int select;
while(1)
{
printf ("***********请按照提示信息选择你所想要的排序方式*************\n");
printf(" 输入1---直接插入排序\n");
printf(" 输入2---折半插入排序\n");
printf(" 输入3---冒泡排序 \n");
printf(" 输入4---快速排序 \n");
printf(" 输入5---简单选择排序\n");
printf(" 输入6---堆排序 \n");
printf(" 输入0---退出 \n");
printf("**************************************************************\n");
printf(" 请输入要选择的排序方式:\n");
scanf(" %d",&select);
if(select>=1&& select<=6)
menu(L,select);
else
break;
}

}

Answer 4

百度，罗塞塔代码的网站，与专家撰写的各种算法的详细版本。

Answer 5

C排序算法
http://wenku.baidu.com/view/566277275901020207409ca2.html

Answer 6

找本算法设计的书，排序算法很全的