sort.cpp

算法代码

#include <stdlib.h> 
#include <stdio.h> 
#include <windows.h> 
#include<iostream> 
#define K 10000        //随机生成的正整数的范围(0到K)
#define N 100           //随机生成的正整数的个数
using namespace std;
//int N=100;
int time0,time1;	           //计时函数

void print( int p[])  //输出生成的序列
{
	int i;
	for(i=0;i<N;i++)
	{
	 cout<<p[i]<<"   ";
	 if((i+1)%10==0)cout<<endl;
	}
}
void creat(int p[])  //生成N个1到1000的正整数
{   int m,n,i;
    m=1;n=K-1; 
	for(i=0;i<N;i++)
	{p[i]=rand()%n+m;   
	}
//	cout<<"创建数组结束"<<endl;
}

void INSERTIONSORT(int A[]) //插入排序
{
	int i,j,key;
	for(j=1;j<N;j++)
	{
		key=A[j];
		i=j-1;
		while(i>=0&&A[i]>key)
		{
			A[i+1]=A[i];
			i--;
		}
		A[i+1]=key;
	}
}
/*
int PARTITION(int A[],int p,int r)   //书上的PARTITION算法，运行的结果很不好。不但出现指针数组方面的错误，而且排序并不正确
{
	int x,i,j,k;
	x=A[r];
	i=p-1;
	for(j=p;j<r-1;j++)
	{
		if(A[j]<=x)
		{
			i=i+1;
			k=A[j];A[j]=A[i];A[i]=k;
		}
	}
	k=A[r];A[r]=A[i+1];A[i+1]=k;
	return i+1;
}
*/
int PARTITION(int array[],int low, int high) //自己另外学的算法
{
 int tmp = array[low];
 int pivotkey = array[low];
 while (low < high) 
 {
  while (low < high && array[high] >= pivotkey) --high;
  array[low] = array[high];
  while (low < high && array[low] <= pivotkey) ++low;
  array[high] = array[low];
 }
    array[low] = tmp;
 return low;
}


void QUICKSORT(int A[],int p,int r)  //快速排序
{
	int q;
	if(p<r)
	{
		q=PARTITION(A,p,r);
		QUICKSORT(A,p,q-1);
		QUICKSORT(A,q+1,r);
	}
}
void INSERTIONSORT1(int A[],int n) //基数排序中的插入排序
{
	int i,j,key,p,q;
	for(j=1;j<N;j++)
	{
		p=key=A[j];
		if(n==1)p=p%10;
        else if(n==2)p=(p/10)%10;        
		else if(n==3)p=(p/100)%10;        
		else p=(p/1000)%10;
		i=j-1;
		q=A[i];		
		if(n==1)q=p%10;
        else if(n==2)q=(q/10)%10;        
		else if(n==3)q=(q/100)%10;        
		else q=(q/1000)%10;
		while(i>=0&&q>p)
		{
			A[i+1]=A[i];
			i--;
			q=A[i];		
		    if(n==1)q=p%10;
            else if(n==2)q=(q/10)%10;        
		    else if(n==3)q=(q/100)%10;        
		    else q=(q/1000)%10;

		}
		A[i+1]=key;
	}
}
void RADIXSORT(int A[])       //基数排序
{
	int i;
	for(i=1;i<5;i++)
	{
		INSERTIONSORT1(A,i); //对第i位进行排序
	}
}
int B[N],C[K];
void COUNTINGSORT(int A[])//计数排序
{
	int i,j,k;
	k=A[0];

	for(i=0;i<K;i++)C[i]=0;	
	for(j=0;j<N;j++)C[A[j]]=C[A[j]]+1;
	for(i=1;i<K;i++) C[i]=C[i]+C[i-1];
	for(j=N-1;j>=0;j--)
	{
		B[C[A[j]]-1]=A[j];//计数的第一位是10  数组没有该元素......a[j]-1倒是有
		C[A[j]]=C[A[j]]-1;
	}
//	cout<<"以下为计数排序结果"<<endl;
	A[0]=k;
//	print(B);
}

void main()
{ 
  int num[N];
  int t;

  creat(num);cout<<"开始快速排序"<<endl;	
  time0=time1=GetTickCount();
  QUICKSORT(num,0,N);
  time1=GetTickCount();
  t=time1-time0;
  cout<<"快速排序所用时间为："<<t<<"毫秒"<<endl;
  cout<<"以下为快速排序结果"<<endl;
  print(num);


//  system("PAUSE");

 
  creat(num);cout<<"开始基数排序"<<endl;	
  time0=time1=GetTickCount();
  RADIXSORT(num);
  time1=GetTickCount();
  t=time1-time0;
  cout<<"基数排序所用时间为："<<t<<"毫秒"<<endl;
  cout<<"以下为基数排序结果"<<endl;
  print(num);

  creat(num);cout<<"开始计数排序"<<endl;	
  time0=time1=GetTickCount();
  COUNTINGSORT(num);
  time1=GetTickCount();
  t=time1-time0;
  cout<<"计数排序所用时间为："<<t<<"毫秒"<<endl;
  cout<<"以下为快速排序结果"<<endl;
  print(num);

  creat(num);cout<<"开始插入排序"<<endl;	
  time0=time1=GetTickCount();
  INSERTIONSORT(num); 
  time1=GetTickCount();
  t=time1-time0;  
  print(num);
  cout<<"插入排序所用时间为："<<t<<"毫秒"<<endl;
  cout<<"以下为快速排序结果"<<endl;
 // system("PAUSE");

}