学步园

//调试用输出
template <class Type>
void Print(Type a[], unsigned int n)
{
cout<<endl;
for(int i=0; i<n; i++)
{
   cout.width(4);
   cout<<a[i];
}
cout<<endl;
}

//冒泡排序(升序)
//时间复杂性O(n*n)
template <class Type>
void BubbleSort(Type a[], unsigned int n)
{
unsigned int i,j;
Type temp;
for(i=n-1; i>0; i--)
{
   for(j=0; j<i; j++)
   {
    if(a[j] > a[j+1])
    {
     temp = a[j];
     a[j] = a[j+1];
     a[j+1] = temp;
    }
   }
}
}

//简单选择排序
//
template <class Type>
void SelectSort(Type a[], unsigned int n)
{
unsigned int i,j,pos;
Type min;
for(i=0; i<n-1; i++)
{
   min = a[i];
   pos = i;
   for(j=i; j<n; j++)
   {
    if(min > a[j])
    {
     min = a[j];
     pos = j;
    }
   }
   if(pos != i)
   {
    a[pos] = a[i];
    a[i]   = min;
   }
}
}

//直接插入排序
//
template <class Type>
void InsertSort(Type a[], unsigned int n)
{
unsigned int i,j;
Type temp;
for(i=1; i<n; i++)
{
   if(a[i] < a[i-1])
   {
    temp = a[i];
    a[i] = a[i-1];
    for(j=i-2; a[j]>temp; j--)
     a[j+1] = a[j];
    a[j+1] = temp;
   }
}
}
//折半插入排序
//
template<class Type>
void BinaryInsertSort(Type a[], unsigned int n)
{
unsigned int i,j;
Type temp;
for(i=1; i<n; i++)
{
   if(a[i] < a[i-1]){
    temp = a[i];
    unsigned int high=i-1, low=0;
    unsigned int mid = low;
    while(high > low)
    {
     mid = low+ (high - low)/2;
     if(temp > a[mid])
      low = mid +1;
     else
      high = mid;
    }
    for(j=i-1; j>=high; --j)
     a[j+1] = a[j];
    a[++j] = temp;
   }
}
}

//快速排序
//
template<class Type>
unsigned int Partition(Type a[], unsigned int low, unsigned int high)
{
Type keyport = a[low];
while(high > low)
{
   while(high>low && keyport<=a[high])   high--;
   a[low] = a[high];
   while(high>low && keyport>=a[low])   low++;
   a[high] = a[low];
}
a[low] = keyport;
return low;
}

template<class Type>
void QSort(Type a[], unsigned int low, unsigned int high)
{
if(high > low)
{
   unsigned int key = Partition(a, low, high);
   if(key == low || key == high)
   {
    if(key == low)
     QSort(a, key+1, high);
    else
     QSort(a, low, key-1);
   }
   else
   {
    QSort(a, low, key-1);
    QSort(a, key+1, high);
   }
}
return;
}

template<class Type>
void QuickSort(Type a[], unsigned int n)
{
QSort(a,0,n-1);
return;
}

//------------------
template<class Type>
void MainFace(Type a[], unsigned int n)
{
Type *b = new Type[n];
for(unsigned int i=0; i<n; i++)
   b[i] = a[i];
char ch,y;
do{
   Print(a,n);
   cout<< "排序算法的测试"<<endl<<
     "1.冒泡排序" <<endl<<
     "2.直接插入排序"<<endl<<
     "3.折半插入排序"<<endl<<
     "4.快速排序" <<endl<<
     "5.简单选择排序"<<endl<<
     "按其他任意键退出/n请选择：";
   cin>>ch;
   switch(ch){
    case '1':
     BubbleSort<Type>(b,n);
     Print(b,n);
     break;
    case '2':
     InsertSort<Type>(b,n);
     Print(b,n);
     break;
    case '3':
     BinaryInsertSort<Type>(b,n);
     Print(b,n);
     break;
    case '4':
     QuickSort<Type>(b,n);
     Print(b,n);
     break;
    case '5':
     SelectSort<Type>(b,n);
     Print(b,n);
     break;
    default:
     return;
   }
   cout<<"是否继续？(y/n) ";
   do{
    cin>>y;
   }while(y!='y'&&y!='Y'&&y!='n'&&y!='N');
}while(y=='y' || y=='Y');
return;
}

void main()
{
cout<<"初始化待排序列/n输入序列个数：";

unsigned int n = 0;
cin>>n;
int *a = new int[n];
cout<<"开始输入待排序序列：/n";
for(unsigned int i=0; i<n; i++)
{
   cout<<"第"<<i+1<<"数:   ";
   cin>>a[i];
}
MainFace<int>(a,n);
return;
}