/*
题目：2、排序算法比较 （必做）
设计要求：利用随机函数产生N个随机整数（N = 500，1000，1500，2000，2500，…,30000），
利用直接插入排序、折半插入排序，起泡排序、快速排序、选择排序、堆排序，基数排序七种排序方法
（可添加其它排序方法）进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的时间。
时间：2008年1月6日 作者：付斌 学号：040640319*/
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#define Maxsize 50000
typedef struct
{
int key;
}Redtype;
typedef struct
{
Redtype r[Maxsize+1];
int length;
}Sqlist;
void Initlist(Sqlist &L,int n) //初始化表(参数n为要参加排序的数的个数)
{
int i;
srand( (unsigned)time( NULL ) ); //随机产生种子
for(i=1;i
L.r[i].key=n*rand()/(n+1.0); // rand()产生伪随机数0 到n
L.length=n+1;
}//Initlist
void Printlist (Sqlist L )
{
int i;
printf("排序后的线性表为：");
for (i=1;i
printf("%d ",L.r[i]);
}
void Insertionsort(Sqlist L) //直接插入排序（书上的算法）
{
int i,j;
for(i=2;i
if( L.r[i].key {
L.r[0]=L.r[i]; //复制为哨兵
L.r[i]=L.r[i-1];
for(j=i-2;L.r[0].key
L.r[j+1]=L.r[j]; //记录后移
L.r[j+1]=L.r[0]; //插入到正确位置
}
//Printlist (L); //测试用
}//Insert_Sort
void Binsertsort(Sqlist L) //折半排序（书上的算法）
{
int i,j;
int low,high;
for(i=2;i
{
L.r[0]=L.r[i]; //将L.r[i]暂存到L.r[0]
low=1;
high=i-1;
while(low
{
int m=(low+high)/2; //折半
if(L.r[0].key
high=m-1;
else //插入点在高半区
low=m+1;
}
for(j=i-1;j>=high+1;--j)
L.r[j+1]=L.r[j]; //记录后移
L.r[high+1]=L.r[0]; //插入
}
//Printlist (L); //测试用
}//Binsert_sort
void Electsort(Sqlist L) //选择排序
{
int min,j;
for(int i=1;i
{
min=i;
for(j=min+1;j
if(L.r[min].key>L.r[j].key)
min=j;
if(min!=i) //判断min与i是否相等，若＝则说明原假设正确反之交换数值
{
L.r[0]=L.r[min];
L.r[min]=L.r[i];
L.r[i]=L.r[0]; //L.r[i]作一个temp，
}
}
//Printlist (L); //测试用
}//Elect_sort
void Bubblesort(Sqlist L) //普通冒泡排序
{
int i,j;
for(i=1;i
for(j=1;j
if(L.r[j].key>L.r[j+1].key)
{
L.r[0]=L.r[j];
L.r[j]=L.r[j+1];
L.r[j+1]=L.r[0];
}
//Printlist (L); //测试用
}//Bubble_sort
void Heapadjust(Sqlist &L,int s,int m) //堆排序中的筛选
{
int j,rc;
rc=L.r[s].key;
for(j=s*2;j
{
if(j
++j;
if(rc>L.r[j].key) //L.r[0]应当插入在位置s上
break;
L.r[s]=L.r[j];
s=j;
}
L.r[s].key=rc; //插入
}
void Heapsort(Sqlist L) //堆排序（书上算法）
{
int i,t;
for(i=L.length/2;i>0;--i)
Heapadjust(L,i,L.length);
for(i=L.length;i>1;--i)
{
t=L.r[1].key;
L.r[1]=L.r[i];
L.r[i].key=t;
Heapadjust(L,1,i-1);
}
//Printlist (L); //测试用
}//Heap_sort
int Partition(Sqlist &L,int low,int high)
{
int pivotkey;
L.r[0]=L.r[low];
pivotkey=L.r[low].key;
while(low {
while(low=pivotkey) --high;
L.r[low]=L.r[high];
while(low
L.r[high]=L.r[low];
}
L.r[low]=L.r[0];
return low;
}//Partition;
void Quicksort(Sqlist &L,int low,int high)
{
int pivotloc;
if (low
{
pivotloc=Partition(L,low,high);
Quicksort(L,low,pivotloc-1);
Quicksort(L,pivotloc+1,high);
}
}//Quicksort
void main()
{
Sqlist List;
clock_t starttime; //开始计时的变量
clock_t endtime; //结束计时的变量
double totaltime1,totaltime2,totaltime3,totaltime4,
totaltime5,totaltime6,totaltime7; //计时变量
int i,number; //排序数的个数
char ch;
printf("输入要随机排序数的个数: ");
scanf("%d", &number);
printf("\n请稍后...正在计算排序时间...\n");
Initlist(List,number);
starttime=clock(); //直接插入排序
Insertionsort(List);
endtime=clock();
totaltime1=(double)(endtime-starttime)/1000;
starttime=clock(); //折半插入排序
Binsertsort(List);
endtime=clock();
totaltime2=(double)(endtime-starttime)/1000;
starttime=clock(); //选择排序
Electsort(List);
endtime=clock();
totaltime3=(double)(endtime-starttime)/1000;
starttime=clock(); //冒泡排序
Bubblesort(List);
endtime=clock();
totaltime4=(double)(endtime-starttime)/1000;
starttime=clock(); //堆排序
Heapsort(List);
endtime=clock();
totaltime5=(double)(endtime-starttime)/1000;
starttime=clock(); //快速排序
Quicksort(List,1,List.length-1);
endtime=clock();
totaltime6=(double)(endtime-starttime)/1000;
printf("\n“直接插入排序”的时间是: %f s \n\n",totaltime1);
printf("\n“折半插入排序”的时间是: %f s \n\n",totaltime2);
printf("\n“选择排序”的时间是: %f s \n\n",totaltime3);
printf("\n“普通冒泡排序”的时间是: %f s\n \n",totaltime4);
printf("\n“堆排序”的时间是: %f s\n \n",totaltime5);
printf("\n“快速排序”的时间是: %f s\n \n",totaltime6);
printf("是否需要打印出排序后的随机序列？(Y/N)\n");
scanf("%s",&ch);
if(ch=='Y'||ch=='y')
Printlist (List);
else
{
printf("如需从新排列请输入1；\n");
printf("如要退出该程序请出入0；\n");
scanf("%s",&ch);
if(ch=='1')
}
}
