排序比较.cpp

对快速

#include  <iostream>
#include  <time.h>
#include  <conio.h>
using namespace std;


class Sort
{
private:
 int *base;
 int *arr;
 int length;
 int data_type;
 bool is_display;
    void HeapAdjust(int , int) ;          //堆调整
 void Partition(int , int);           //快速排序的数组分割
public:

 Sort(int size, int kind,char display);     //分配数组内存
 ~Sort();                       //释放分配的内存
 void Show();               //显示数组的值
 bool Copy();                                //内存拷贝
 void Display();                             //最后输出显示
 void RunTime(int runtime){cout<<"花费时间"<<(long double) runtime/CLOCKS_PER_SEC<<endl;}  //计算排序算法运行时间
  void BubbleSort();                  //冒泡排序
  void QuickSort();      //快速排序
  void  HeapSort();                  //堆排序
  void  SelectionSort();            //选择排序
  void  InsertSort();              //插入排序
  void  ShellSort();              //希尔排序
  void  RadixSort();             //基数排序
  void  mysort();
 
};

Sort::Sort(int size = 100,int kind = 0,char display = 'N')
{
 int i;
 length = size;
 data_type = kind;
 if(display == 'Y' || display == 'y')
  is_display = true;
 else
  is_display = false;

  //基于base数组分配内存并赋随机值
 base = (int*)malloc(sizeof(int)*size);
 if(!base)                      
 {
  cerr<<"The system malloc memory error!"<<endl;
     exit(1);
 }
 switch(kind)           //base数组赋值类型选择(0--随机值    1--正序      2--逆序)
 {
 case 0:
	 i = clock();
	 srand(i);
  for(i = 0;i<size;i++)
	  base[i] =::rand();
  break;
 case 1:
	 for(i = 0;i<size;i++)
		 base[i] = i;
		 break;
 case 2:
  for(i = 0;i < size;i++)
   base[i] = (size - i);
  break;
 default:
  break;
 }
 
 //基于arr数组分配内存并赋0值
 arr = (int*)malloc(sizeof(int)*length);     
 if(!arr)
 {
  cerr<<"The system malloc memory error!"<<endl;
  exit(1);
 }
memset(arr,0,sizeof(arr));
}


Sort::~Sort()
{
 free(base);
 free(arr);
}

/*    显示arr数组值   */
void Sort::Show()
{
 int i;
 if(is_display)
 {
  system("PAUSE");
    for(i = 0;i < length;i++)
  cout<<arr[i]<<'\t';
         cout<<endl<<endl<<endl;
 }
 

}

/* 数组拷贝    */
bool Sort::Copy()
{
 int i;

 for(i = 0;i<length;i++)
  arr[i] = base[i];
 return true;
}

/*  冒泡排序    */
void Sort::BubbleSort()
{
 int i,j,t;
 for(i = 0;i<length;i++)
  for(j = i;j<length;j++)
   if(arr[i]>arr[j])
   { t = arr[i]; arr[i] = arr[j]; arr[j] = t; }
 
}

void Sort::mysort()
{
		int max,min,*q,i,temp,length1,j;
		max=min=arr[0];
		for(i=1;i<length;i++)
		{
			if(arr[i]>max)
			{
				max=arr[i];
			}
			else if(arr[i]<min)
			{
				min=arr[i];
			}
		}
		max=1000000;
		length1=max-min+2;
		temp=min-1;
		q=(int *)calloc(length1,sizeof(int));
		for(i=0;i<length1;i++)
		{
			q[i]=0;
		}
		for(i=0;i<length;i++)
		{
			q[arr[i]-temp]+=1;
		}
		j=0;
	    for(i=0;i<length1;i++)
		{
		    	if(q[i]==1)
				{
			    	arr[j]=i+temp;
			    	j+=1;
				}
		    	else if(q[i]>1)
				{
			    	while(q[i]--)
					{
				    	arr[j]=i+temp;
				    	j+=1;
					}
				}		
		}
}    
/*   快速排序   */

void Sort::Partition(int low,int high)
{
 int i,j,t;
 
 if(low<high)
 {
  i = low ; j = high;
  t = arr[low];
 while(i<j)
 {
  while(i<j&&arr[j]>t) j-- ;
  if(i<j) 
   arr[i++] = arr[j];
  while(i<j&&arr[i]<=t) i++ ;
  if(i<j) 
   arr[j--] = arr[i];
 }
 arr[i] = t;
 Sort::Partition(low,i-1);
 Sort::Partition(i+1,high);
 }
}
void Sort::QuickSort()
{
 Sort::Partition(0,length -1 );
 
}


/*   堆排序            */

void  Sort::HeapAdjust(int k, int n)
{
int i,j;
 int tmp;
 i=k;
 j=2*i+1;
 tmp=arr[i];
 while(j<n)
 {
  if((j<n-1)&&(arr[j]<arr[j+1]))
   j++;
  if(tmp<arr[j])
  {
   arr[i]=arr[j];
   i=j;
   j=2*i+1;
  }
  else
   break;
 }
 arr[i]=tmp;
}

void  Sort::HeapSort()
{
  int k, des;
 long tmp;
     int n = length;

 for(k=n/2-1;k>=0;k--)  /*建堆*/
  Sort::HeapAdjust(k, n);

 for(des=n-1;des>0;des--) /*排序*/
 {
  tmp=arr[0];
  arr[0]=arr[des];
  arr[des]=tmp;
  Sort::HeapAdjust(0,des);
 }
}

// 选择排序     

void  Sort::SelectionSort()
{
 int i,j,t,mins = 0;
 for(i = 0;i < length;i++)
 {
  int mins = i;
  for(j = i+1;j<length;j++)
   if(arr[j]<arr[mins]) mins = j;
  t = arr[i]; arr[i] = arr[mins]; arr[mins] = t;
 }
}


//  插入排序      
void  Sort::InsertSort()
{
 int i,j,t;
 for(i = length -1; i>0; i--)     //确定arr数组中最小值，并放在arr[0]做哨兵位
  if(arr[i] < arr[i-1]) 
  {t = arr[i]; arr[i] = arr[i-1]; arr[i-1] = t;}
 for(i = 2; i<length; i++)
 {
  int j = i; t = arr[i];
  while(t<arr[j-1])
  {
   arr[j] = arr[j-1]; j--;
  }
  arr[j] = t;
 }
}

// 希尔排序      
void Sort::ShellSort()
{
 int i,j,h,v;
 for(h = 1; h <= length / 9; h = 3*h+1);     //查找确定最大增量值
 for(; h>0;h /= 3)
  for(i = h; i < length; i++)    //直接插入排序的一种改进（与直接插入排序比较）
  {
   j = i; v = arr[i];
   while(j >= h && v<arr[j-h])
   {
    arr[j] = arr[j-h]; j -= h;
   }
   arr[j] = v;
  }
}


// 基数排序
void Sort::RadixSort()
{
 int keysize=5;
 int n = length;
 int i,j,k,t;
 int d,e,m=0;
 int *c[10],z[10];

 for (i=0;i<10;i++)
  c[i]=(int*)malloc(sizeof(int)*n);

 for(i=0;i<keysize;i++)
 {
  memset(z,0,sizeof(z));
  for(j=0;j<n;j++)
  {
   k=arr[j];
   for (t=0;t<i;t++)
    k=k/10;
   k=k%10;
   *(c[k]+z[k])=arr[j];
   z[k]++;
  }

  m=0;
  for(d=0;d<10;d++)
  {
   for(e=0;e<z[d];e++)
   {
    arr[m]=*(c[d]+e);
    m++;
   }
  }
 }

 for (i=0;i<10;i++)
  free(c[i]);
}

void  Sort::Display()
{
 int start_time, end_time;



    
cout<<"--------－快速排序----------"<<endl;
 if(data_type == 0)
 {
 Sort::Copy();
 start_time = clock();
 Sort::QuickSort();
 end_time = clock();
 Sort::RunTime(end_time - start_time);
 Sort::Show();
 }
 else
  cerr<<"正反序情况时，快速排序可能会导致堆栈溢出，故屏蔽测试"<<endl<<endl;


  cout<<"--------－我的排序------------"<<endl;
 Sort::Copy();
 start_time = clock();
 Sort::mysort();
 end_time = clock();
 Sort::RunTime(end_time - start_time);
 Sort::Show();

 cout<<"--------－堆排序------------"<<endl;
 Sort::Copy();
 start_time = clock();
 Sort::HeapSort();
 end_time = clock();
 Sort::RunTime(end_time - start_time);
 Sort::Show();

  
 cout<<"--------－希尔排序----------"<<endl;
 Sort::Copy();
 start_time = clock();
 Sort::ShellSort();
 end_time = clock();
 Sort::RunTime(end_time - start_time);
 Sort::Show();


 cout<<"--------－基数排序----------"<<endl;
 Sort::Copy();
 start_time = clock();
 Sort::RadixSort();
 end_time = clock();
 Sort::RunTime(end_time - start_time);
 Sort::Show();

  cout<<"--------－插入排序----------"<<endl;
 Sort::Copy();
 start_time = clock();
 Sort::InsertSort();
 end_time = clock();
 Sort::RunTime(end_time - start_time);
 Sort::Show();


cout<<"----------选择排序-----------"<<endl;
 Sort::Copy();
 start_time = clock();
 Sort::SelectionSort();
 end_time = clock();
 Sort::RunTime(end_time - start_time);
 Sort::Show();


 cout<<"-----------冒泡排序---------"<<endl;
 Sort::Copy();
 start_time = clock();
 Sort::BubbleSort();
 end_time = clock();
 Sort::RunTime(end_time - start_time);
 Sort::Show();


}

 

int main()
{ 
 int size,kind;
 bool ct;
 char sz = 'N',ch;
 do{
 cout<<" 输入测试的试验数据个数: (N>0) "<<endl;
 do{
 cin>> size;
 }while(size<1&&(cout<<"数据个数应该大于1,请重新输入:"<<endl));

 cout<<" 输入测试类型值 : (0--随机数   1--正序  2--逆序) "<<endl;
 do{
 cin>>kind;
 }while(((kind>2)||(kind<0))&&(cout<<"类型值范围(0-2),请重新输入:"<<endl));

 if(size<50000)
 {
 cout<<" 是否显示排序结果(Y/N):"<<endl;
 do{
  cin>>sz;
 } while((sz!= 'Y' && sz!= 'N' && sz != 'y' && sz!= 'n')&&(cout<<"请输入(Y or N):"<<endl));
 }
 else
  cout<<"输出测试值太多( >50000 ),没有必要显示"<<endl<<endl<<endl;;
 Sort t(size,kind,sz);
 t.Display();
 cout<<endl<<"是否继续？(Y/N)"<<endl;
 do{
  cin>>ch;
 } while((ch!= 'Y' && ch!= 'N' && ch != 'y' && ch!= 'n')&&(cout<<"请输入(Y or N):"<<endl));
 if(ch == 'Y' || ch == 'y')
  ct = true;
 else
  ct = false;
}while(ct == true);
 return 0;
system("PAUSE");
}