#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(); //基数排序
};
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::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::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();
}
void 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);
system("PAUSE");
}
