1.实验内容

用任意一种排序方式给出n个整数按升序排序后的结果，满足以下要求：

1.不得使用与实验相关的STL；

2.需使用类模版(template<class T>)；

3.需定义排序类，封装各排序方法；

4.排序数据需使用动态数组存储；

5.排序类需提供以下操作：名次排序、及时终止的选择排序、及时终止的冒泡排序、插入排序。

2.测试结果

输入：

5

2 4 3 5 1

输出：

1 2 3 4 5

3.源代码

#include<iostream>

using namespace std;

template<class T>

class order

{

private:

int num;

public:

order(int n)

{

if(n<0) num=0;

else num=n;

}

~order()

{

}

//以下"名次"表示从小到大的名次

void swap(T &x,T &y)

//交换函数，将两个变量的值交换

{

int temp=x;

x=y;

y=temp;

}

void compare(T *a,int n,int *r)

//比较函数，计算数组a中每个元素的名次，将名次存入数组r中

{

int i,j;

for(i=0;i<n;i++)

{

int k=0;

for(j=0;j<n;j++) if((j<i&&a[j]==a[i])||a[j]<a[i]) k++;

//计算比a[i]小或者与a[i]相等但在a[i]左侧的元素个数并记入k

r[i]=k;

//将名次k赋值给r[i]

}

}

void makeOrder1(T *a,int n)

//名次排序，数组a记录n个元素

{

int *r=new int[n];

compare(a,n,r);

//用数组r记录n个元素的名次

T *b=new T[n];

int i;

for(i=0;i<n;i++) b[r[i]]=a[i];

//将元素按顺序记录在数组b中

for(i=0;i<n;i++) a[i]=b[i];

//将元素按顺序转存在数组a中

delete []b;

delete []r;

}

void makeOrder2(T *a,int n)

//及时终止的选择排序，数组a记录n个元素

{

bool sorted=false;

//数组为无序状态

for(int size=n;!sorted&&(size>1);size--)

//size为参与本次选择排序的元素个数，若sorted值为1，则顺序已排好，循环终止

{

int indexOfMax=0;

//从第1个元素开始比较

sorted=true;

//假定已经排好序

for(int i=1;i<size;i++)

if(a[indexOfMax]<=a[i]) indexOfMax=i;

//若顺序正确，将最大值坐标后移

else sorted=false;

//没有排好序

swap(a[indexOfMax],a[size-1]);

//将最大值移动到size个元素的最右边

}

}

bool bubble(T *a,int n)

//冒泡函数，对n个元素进行第一次冒泡，并返回此次冒泡过程中是否发生交换

{

bool swapped=false;

//未发生交换

for(int i=0;i<n-1;i++)

//将n个元素的最大值移动至最右边

if(a[i]>a[i+1])

{

swap(a[i],a[i+1]);

//交换两个元素

swapped=true;

//已发生交换

}

return swapped;

}

void makeOrder3(T *a,int n)

//及时终止的冒泡排序，数组a记录n个元素

{

for(int i=n;i>1&&bubble(a,i);i--);

//若未发生元素移动，则bubble值为0，顺序已排好，循环终止

}

void makeOrder4(T *a,int n)

//插入排序，数组a记录n个元素

{

int i;

for(i=1;i<n;i++)

//从第2个元素开始，向其左边元素已经完成排序的序列插入这个元素

{

T t=a[i];

int j;

for(j=i-1;j>=0&&t<a[j];j--) a[j+1]=a[j];

a[j+1]=t;

}

}