#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<iostream>
using namespace std;
void find(int *a,int n);
void input(int pIn[], int n);
void del(int *a,int n);
void Swap(int *a, int *b);
int Partition(int a[], int p, int r);
void arrange(int *c,int length);
template <class Type>
/* 为了便于维护，现在把排序封装在类ArraySort内
*/
class ArraySort
{
private: int elem; //elem的值决定按升序还是降序
int len; //排序数组的长度
Type *b; //排序时用与交换的数组
Type *a; //用来存放要排序的数组；
public:
void set(Type c[],int k); //接收要排序的数组及数组长度
void Sort(); //进行排序
void MergeSort(int ,int );
void Merge(int ,int ,int); //进行合并
void Copy(int ,int); //复制一个数组到另一个数组
void ArPrint(); //输出数组元素
void ReturnCopy(Type c[]); //把已经排序数组返回给原数组
~ArraySort();
ArraySort(int k=0){
elem=k;
len=0;
a=NULL;
b=NULL;
}
};
template<class Type>
void ArraySort<Type>::set(Type c[],int k )
{ int m;
len=k;
//len=c.length;
a=new Type[len];
b=new Type[len];
if((a==NULL)||(b==NULL))
{ cout<<"can't allocate more memory,terminating."<<endl;
exit(1);
}
else{
for(int i=0;i<len;i++)
a[i]=c[i];
}
cout<<" input the number 0 or 1:"<<endl;
cout<<"0 min to max:"<<endl;
cout<<"1 max to min"<<endl;
cin>>m;
if(m>=0&&m<=1)
elem=m;
else {
cout<<"You input a illegal number!!";
cout<<" input the number 0 or 1:"<<endl;
cout<<"0 min to max:"<<endl;
cout<<"1 max to min"<<endl;
}
}
template <class Type>
void ArraySort<Type>::Sort()
{
MergeSort(0,len-1);
}
template <class Type>
void ArraySort<Type>::Merge(int left,int m,int right)
{
int i=left,
j=m+1,
k=left;
if(elem==0){
while((i<=m)&&(j<=right))
if(a[i]<=a[j]) b[k++]=a[i++];
else b[k++]=a[j++];
}
else{
while((i<=m)&&(j<=right))
if(a[i]>=a[j]) b[k++]=a[i++];
else b[k++]=a[j++];
}
while(i<=m)
b[k++]=a[i++];
while(j<=right)
b[k++]=a[j++];
}
template <class Type>
void ArraySort<Type>::Copy(int left,int right)
{
for(int i=left;i<=right;i++)
a[i]=b[i];
}
template <class Type>
void ArraySort<Type>::ArPrint()
{
// int len=this.a.length;
cout<<"The length of array is :"<<len<<endl;
cout<<"The elements of array is :"<<endl;
for(int i=0;i<len;i++)
cout<<" "<<a[i];
if(i/5==0)
cout<<endl;
}
template <class Type>
void ArraySort<Type>::MergeSort(int left,int right)
{
if(left<right){
int i=(left+right)/2;
MergeSort(left,i);
MergeSort(i+1,right);
Merge(left,i,right);
Copy(left,right);
}
}
template <class Type>
void ArraySort<Type>::ReturnCopy(Type c[])
{
for(int i=0;i<len;i++)
c[i]=a[i];
}
template <class Type>
ArraySort<Type>::~ArraySort()
{
delete a;
delete b;
}
void qSort(int pIn[], int p/*0*/, int r/*r = N - 1*/);
main()
{ char c;
int i,a[12]={6,11,12,5,1,13,8,9,14,7,10},exit=1;
do
{
system("cls");
for(i=0;i<80;i++)
printf("*");
printf("\t 1:选择排序法\n");
printf("\t 2:冒泡排序法\n");
printf("\t 3:插入排序法\n");
printf("\t 4:合并排序法\n");
printf("\t 5:退出\n");
printf("\t 请选择输入选项【1\\2\\3\\4\\5】:\n");
do
{
c=getch();
}while(c!='1'&&c!='2'&&c!='3'&&c!='4'&&c!='5');
switch(c)
{ case '1':input(a,11);
cout<<endl;
for(i=0;i<11;i++)
cout<<a[i]<<" ";
cout<<endl;
break;
case '2':del(a,11);
cout<<endl;
for(i=0;i<11;i++)
cout<<a[i]<<" ";
cout<<endl;break;
case '3':find(a,11); break;
case '4':arrange(a,11); break;
case '5':exit=0;
}
printf("按任意键返回主菜单:\n");
getche();
}while(exit);
}
void input(int pIn[], int n)
{
qSort(pIn, 0, n-1);
}
void Swap(int *a, int *b){
int c = *a;
*a = *b;
*b = c;
}
int Partition(int a[], int p, int r)
{
int i = p;
int j = r + 1;
int x = a[p];
while(1){
while (i <= r && a[++i] < x); // 如果你要从大到小排序就改x前的<为>
while (j >= p && a[--j] > x); //同时这的>也要改为<
if (i >= j) break;
Swap(&a[i], &a[j]);
}
if (i == j) {
j --;
}
a[p] = a[j];
a[j] = x;
return j;
}
void qSort(int pIn[], int p/*0*/, int r/*r = N - 1*/)
{
if (p < r) {
int q = Partition(pIn, p, r);
qSort(pIn, p, q - 1);
qSort(pIn, q + 1, r);
}
}
void del(int *a,int n)//冒泡
{
int i,j,k;
for(i=0;i<=n-2;i++)
for(j=0;j<=n-2-i;j++)
if(a[j]>a[j+1])//如果你要从大到小排序就改>为<
{
k=a[j];
a[j]=a[j+1];
a[j+1]=k;
}
}
void find(int *a,int n)//插入
{
int i, j, x;
for(i = 1;i < n;i++)
{
x = a[i];
j = i - 1;
while(j >= 0 && a[j] > x){
a[j+1] = a[j];
j--;
}
a[j+1] = x;
}
for(i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
}
void arrange(int *c,int length)//组合
{
int i;
ArraySort<int > as;
as.set(c,length);
cout<<"排序前的数组元素序列："<<endl;
for( i=0;i<length;i++)
cout<<" "<<c[i];
cout<<endl;
as.Sort();
as.ReturnCopy(c);
cout<<"排序后的数组元素序列："<<endl;
for( i=0;i<length;i++)
cout<<" "<<c[i];
cout<<endl;
}
楼主做了我2个多小时啊。。TC不能识别有的头文件哈，我已经用VC6.0测试过了