内部排序算法比较.cpp

内部算法排序比较

				//从小到到的排序 
#include<windows.h>
#include<stdio.h>
#include<time.h>
#include<math.h>
#include<stdlib.h>
#include <algorithm>
#include <functional>
using namespace std;
				#define MAX 10000	//MAX表示最大的数据量
#define INFINITY 10000
int a[MAX];
int store[MAX];
	//用于归并排序
int TR1[MAX];
int TR2[MAX];
void randomizeNum(long n){//N表示要产生的随机数的数目
	long i;
	for(i=0;i<n;i++){
		a[i]=rand()%5000;//控制生成的数据在5000之内
		store[i]=a[i];
 }
}
void restore(long n){
 long i;
 for(i=1;i<n;i++)
 a[i]=store[i];
}
void BubbleSort(long n){//简单的冒泡排序算法
 long i,j;
 int tmp;
 for(i=1;i<n;i++)
  for(j=n-2;j>=i;j--)
   if(a[j+1]<a[j]){
    tmp=a[j+1];
    a[j+1]=a[j];
    a[j]=tmp;
   }
}
void InsertSort(long n){//插入排序
 long i,j;
 for(i=2;i<n;i++)
  if(a[i-1]>a[i]){
  a[0]=a[i];
  a[i]=a[i-1];
  for(j=i-2;a[j]>a[0];j--)
   a[j+1]=a[j];
  a[j+1]=a[0];
 }
}
void BInsertSort(long n){//折半排序法
 long i,j,low,high,m;
 for(i=2;i<n;i++){
  a[0]=a[i];
  low=1;high=i-1;
  while(low<=high){
   m=(low+high)/2;
   if(a[0]<a[m]) high=m-1;
   else low=m+1;
  }
  for(j=i-1;j>=high+1;j--) a[j+1]=a[j];
  a[high+1]=a[0];
 }
}
void ShellInsert(long n,long dk){
 long i,j;
 for(i=dk+1;i<n;i++)
  if(a[i]<a[i-dk]){
   a[0]=a[i];
   for(j=i-dk;j>0&&(a[0]<a[j]);j-=dk)
    a[j+dk]=a[j];
   a[j+dk]=a[0];
  }
}
int CalculateT(long n,long dlta[]){//用于计算希尔排序中的dlta[k]=2^(t-k+1)
 int i,t,k;
 long sum=1;
 for(i=1;i;i++){
  sum=sum*2;
  if(sum>n) break;
 }
 t=i-1;
 for(k=1;k<=t;k++)
  dlta[k]=pow(2,t-k+1)-1;
 return t;
}
void ShellSort(long n,long dlta[],long t){
 int k;
 for(k=1;k<t;k++)
  ShellInsert(n,dlta[k]);
}
long Partition(long n,long low,long high){
 int pivotkey;
 a[0]=a[low];
 pivotkey=a[low];
 while(low<high){
  while(low<high&&a[high]>=pivotkey) high--;
  a[low]=a[high];
  while(low<high&&a[low]<=pivotkey) low++;
  a[high]=a[low];
 }
 a[low]=a[0];
 return low;
}
void QSort(long n,long low,long high){
 long pivotloc;
 if(low<high){
  pivotloc=Partition(n,low,high);
  QSort(n,low,pivotloc-1);
  QSort(n,pivotloc+1,high);
 }
}
void QuickSort(long n){//快速排序
 QSort(n,1,n);
}
void HeapAdjust(long n,int s,int m){//堆调整
 long rc,j;
 rc=a[s];
 for(j=2*s;j<=m;j*=2){
  if(j<m&&a[j]<a[j+1]) j++;
  if(!(rc<a[j])) break;
  a[s]=a[j];s=j;
 }
 a[s]=rc;
}
void HeapSort(long n){
 long i,tmp;
 for(i=n/2;i>0;i--)
  HeapAdjust(n,i,n);
 for(i=n-1;i>1;i--){
  tmp=a[i];
  a[i]=a[1];
  a[1]=tmp;
  HeapAdjust(n,1,i-1);
 }
}
void Merge(int a[],long p,long q,long r){
	long i,j,k,n1,n2;
	n1=q-p+1;n2=r-q;
	for(i=1;i<=n1;i++)
		TR1[i]=a[p+i-1];
	for(j=1;j<=n2;j++)
		TR2[j]=a[q+j];
	TR1[i]=INFINITY;
	TR2[j]=INFINITY;
	i=1;j=1;
	for(k=p;k<=r;k++)
		if(TR1[i]<TR2[j]) {
			a[k]=TR1[i];
			i++;
		}
		else {
			a[k]=TR2[j];
			j++;
		}
	
}
void MSort(int a[],long p,long r){
	long m;
	if(p<r){
		m=(p+r)/2;
		MSort(a,p,m);
		MSort(a,m+1,r);
		Merge(a,p,m,r);
	}
}
int cmp ( const void *a , const void *b ) { //用于C语言自带的qsort测试
	return *(int *)a - *(int *)b; 
} 

void MergeSort(long n){
	MSort(a,1,n);
}
void testSort(long n){//将排序完的数打印出来，测试排序是否正确
 long i;
 for(i=1;i<n;i++)
  printf("%d ",a[i]);
}
int main(){
	DWORD timeStart,timeEnd;
	int t;
	long dlta[100];
	srand((unsigned)time(NULL));
	randomizeNum(MAX);
	printf("\t\t数据量大小：%ld\n",MAX);
	timeStart=GetTickCount();
	BubbleSort(MAX);
	timeEnd=GetTickCount();
	printf("冒泡排序\t:%dms\n",timeEnd-timeStart);

	restore(MAX);
	timeStart=GetTickCount();
	InsertSort(MAX);       
	timeEnd=GetTickCount();
	printf("插入排序\t:%dms\n",timeEnd-timeStart);

	restore(MAX); 
	timeStart=GetTickCount();
	BInsertSort(MAX);
	timeEnd=GetTickCount();
	printf("折半排序\t:%dms\n",timeEnd-timeStart);

	restore(MAX);
	timeStart=GetTickCount();
	t=CalculateT(MAX,dlta);
	ShellSort(MAX,dlta,t);
	timeEnd=GetTickCount();
	printf("希尔排序\t:%dms\n",timeEnd-timeStart);

	restore(MAX);
	timeStart=GetTickCount();
	QuickSort(MAX);
	timeEnd=GetTickCount();
	printf("快速排序\t:%dms\n",timeEnd-timeStart);


	restore(MAX);
	timeStart=GetTickCount();
	HeapSort(MAX);
	timeEnd=GetTickCount();
	printf("堆排序\t\t:%dms\n",timeEnd-timeStart);

	restore(MAX);
	timeStart=GetTickCount();
	 MergeSort(MAX);//归并排序测试失败
	timeEnd=GetTickCount();
	printf("归并排序\t:%dms\n",timeEnd-timeStart);

	timeStart=GetTickCount();
	qsort(a,MAX,sizeof(a[1]),cmp);
    timeEnd=GetTickCount();
	printf("快速排序\t:%dms\t这是C语言自带的快速排序qsort\n",timeEnd-timeStart);

	restore(MAX);
	timeStart=GetTickCount();
	sort(a,a+MAX);//这个是stl中的sort,是C++
    timeEnd=GetTickCount();
	printf("sort排序\t:%dms\t这是stl中的含归并与快速优化排序\n",timeEnd-timeStart);
	return 0;
}