定义一个一维整数数组，其中储存1000个1至100以内的整数

Question

有一个数组a[50]其中没有重复元素，其中元素大于0，小于100!怎么写出几个排序方法？有怎么对数组进行升序排序？

Answer 1

可以用冒泡排序法，最大堆排序，直接选择排序法，直接插入排序法等等啊！！！！#ifndef DATALIST_H
#define DATALIST_H
#include<iostream>
const int DefaultSize=100;
template<class T>
class Element { //数据表元素定义
public:
T key; //排序码
T otherdata; //其他数据成员
Element<T>& operator=(Element<T>& x) //元素x的值赋给this
{key=x.key;otherdata=x.otherdata;return this;}
bool operator==(Element<T>& x) {return key==x.key;} //判*this与x相等
bool operator<=(Element<T>& x) {return key<=x.key;} //判*this小于或等于x
bool operator>(Element<T>& x) {return key>x.key;} //判*this大于x
bool operator<(Element<T>& x) {return key<x.key;} //判*this小于x
};template<class T>
class dataList { //数据表类定义
public:
dataList(int maxSz=DefaultSize):maxSize(maxSz),currentSize(0)
{Vector=new Element<T>[maxSize];} //构造函数
void Swap(Element<T>& x,Element<T>& y) //交换x,y
{Element<T>temp=x;x=y;y=temp;}
int Length() {return currentSize;} //取表长度
Element<T>& operator[](int i) {return Vector[i];} //取第i个元素
int Partition(const int low,const int high); //快速排序划分
private:
Element<T>* Vector; //存储排序元素的向量
int maxSize; //向量中最大元素个数
int currentSize; //当前元素个数
};
#endif
template<class T>
void merge(dataList<T>& L1,dataList<T>& L2,
const int left,const int mid,const int right) {
//L1.Vector[left:mid]与L1.Vector[mid+1:right]是两个有序表归并
//成一个有序表L1.Vector[left:right]。
for(int k=left;k<=right;k++)
L2[k]=L1[k];
int s1=left,s2=mid+1,t=left; //s1,s2是检测指针，t是存放指针
while(s1<=mid&& s2<=right) //两个表都未检测完，两两比较
if(L2[s1]<=L2[s2]) L1[t++]=L2[s1++];
else L1[t++]=L2[s2++];
while(s1<=mid) L1[t++]=L2[s1++]; //若第一个表未检测完，复制
while(s2<=right) L1[t++]=L2[s2++]; //若第二个表未检测完，复制
};
template<class T>
void mergeSort(dataList<T>& L,dataList<T>& L2,int left,int right) {
if(left>=right) return;
int id=(left+right)/2; //从中间划分为两个子序列
mergeSort(L,L2,left,mid); //对左侧子序列进行递归排序
mergeSort(L,L2,mid+1,right); //对右侧子序列进行递归排序
merge(L,L2,left,mid,right); //合并
};void bubblesort(int a[],int n)
{
int p=0,q=0;
for(int j=0;j<n-1;j++)
{
for(int i=0;i<n-1-j;i++)
{
if(a[i]>a[i+1])
{
int temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
p++;
}
q++;
}
}
cout<<"冒泡排序后结果：";
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
cout<<"比较次数："<<q<<endl;
cout<<"交换次数："<<p<<endl;
}
void binaryinsertsort(int a[], int n)
{
int i, j;
int p=0,q=0;
int low, high, mid;
int temp;
for (i=1; i<n; i++)
{
temp = a[i];
low = 0;
high = i - 1;
while (low <= high) //在a[low。。。high]中折半查找有序插入的位置
{
mid = (low + high) / 2;
if (a[mid] > temp)
high = mid - 1;
else
low = mid + 1;
q++;
}

for (j=i-1; j>high; j--)
{//元素后移
a[j+1] = a[j];
p++;
}

a[high+1] = temp; //插入
}
cout<<"折半排序后结果：";
for( i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
cout<<"比较次数："<<q<<endl;
cout<<"交换次数："<<p<<endl;
}
void insertsort(int R[],int n)
{
int p=0,q=0;
for(int t=1;t<n;t++)
{
if(R[t]<R[t-1])
{
int temp=R[t];
int j=t-1;
do
{
R[j+1]=R[j];
j--;
}while(temp<R[j]&&j>=0);
R[j+1]=temp;
p++;

}
q++;
} cout<<"直接插入排序后结果：";
for(int i=0;i<n;i++)
{
cout<<R[i]<<" ";
}
cout<<endl;
cout<<"比较次数："<<q<<endl;
cout<<"交换次数："<<p<<endl;
}
void selectsort(int a[],int n)
{
int p=0,q=0;
for(int i=0;i<n;i++)
{
int k=i;
for(int j=i+1;j<n;j++)
{
if(a[j]<a[k])
{
k=j;

}q++;
}
if(k!=i)
{
swap(a[i],a[k]);
p++;
}
}
cout<<"直接选择排序后结果：";
for(i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
cout<<"比较次数："<<q<<endl;
cout<<"交换次数："<<p<<endl;
}void shellsort(int a[], int len)
{
int p=0,q=0;
for (int increment=len/2; increment>0; increment/=2)
{
for (int i=increment; i<len; i++)
{
int temp = a[i];
int j = i;
for (; j>=increment; j-=increment)//元素后移
{
if (temp < a[j-increment])
a[j] = a[j-increment];
else
break;
q++;
}
a[j] = temp; //插入
p++;
}//for
}//for
cout<<"希尔排序后结果：";
for(int i=0;i<len;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
cout<<"比较次数："<<q<<endl;
cout<<"交换次数："<<p<<endl;
}
#include<iostream>
using namespace std;
#include"dataList.h"void main()
{
int n,k;
cout<<"输入数组个数:";
cin>>n;
int a[100];
cout<<"输入数组元素：";
for(int i=0;i<n;i++)
{
cin>>a[i];
}
cout<<"请选择需要使用的排序方法："<<endl;
cout<<"1.冒泡排序法 2.折半排序法 3.希尔排序法 4.直接插入排序法 5.直接选择排序法"<<endl;
cout<<"请输入序号：";
cin>>k;
switch(k)
{
case 1:
bubblesort(a,n);
cout<<endl;
break;
case 2:
binaryinsertsort(a,n);
cout<<endl;
break;
case 3:
shellsort(a,n);
cout<<endl;
break;
case 4:
insertsort(a,n);
cout<<endl;
break;
case 5:
selectsort(a,n);
break;
}
}