#include<iostream>
using namespace std;

template<class T>
void bubbleSortUp(T *a,int n){
	for(int i=n-1;i>0;i--){     //从n-1到1（大于0）
		for(int j=0;j<i;j++){   //第二个循环从 0~i开始
			if(a[j]>a[j+1]){    //如果顺序不对，交换内容
				T temp;         //交换用临时变量
				temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
			}
		}
	}	
}

template<class T>
void bubbleSortDown(T *a,int n){
	for(int i=n-1;i>0;i--){
		for(int j=0;j<i;j++){
			if(a[j]<a[j+1]){    //降序
				T temp;
				temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
			}
		}
	}
}

template<class T>
void print(const T *a,int n){
	for(int i=0;i<n;i++){
		cout<<a[i]<<" ";
	}
}


int main(){
	double p[]={4.2,2.3,3.1,1.1,3.1,5,7,8};
	bubbleSortUp(p,sizeof(p)/sizeof(double)); //sizeof(p)/sizeof(double)取数组长度
	print(p,sizeof(p)/sizeof(double));
	float p2[]={1,3,2,2,4.4,99.2,13.84,5,6};
	cout<<endl;
	bubbleSortDown(p2,sizeof(p2)/sizeof(p2[0]));
	print(p2,sizeof(p2)/sizeof(p2[0]));
	return 0;
}

#include<iostream>
using namespace std;
template<class T>
void fun(T *p,int n){
	for(int i=1;i<n;i++){
		T temp =p[i];        //存储当前的数
		for(int j=0;j<i;j++){//从第一个开始比较(a[0]不用排列)
			if(temp<p[j]){   //找到排列的位置
				int k=i;
				while(k!=j){ //i=j时停止
					p[k]=p[k-1];//j后的元素向后移动，腾出位置
					k--;
				}
				p[j]= temp;  //填入值
				break;
			}
			
		}
	}	
}
template<class T>
void jiangxu(T *p,int n){    //指针、长度
	for(int i=1;i<n;i++){    //用于控制数 
		T temp = p[i];       //用于存放这个变量，移动时不破坏
		for(int j=0;j<i;j++){//和已经排雷好的数比较，从0开始，小于i（i前已经排列好）
			if(temp>p[j]){   //如果找见位置，则向后移冬
				int k =i;    //存储当前的i的值
				while(k!=j){ //控制向后移，知道相等
					p[k]=p[k-1];
					k--;
				}
				p[j]=temp;
				break;       //退出循环
			}
		}
	}
}

template<class T>
void output(const T *p,int n){
	for(int i=0;i<n;i++){
		cout<<p[i]<<" ";
	}
}
int main(){
	double p[]={4.2,2.3,3.1,1.1,3.1,5,7,8};
	fun(p,sizeof(p)/sizeof(double));     //sizeof(p)/sizeof(double)取数组长度
	output(p,sizeof(p)/sizeof(double));
	float p2[]={1,3,2,2,4.4,99.2,13.84,5,6};
	cout<<endl;
	jiangxu(p2,sizeof(p2)/sizeof(p2[0]));
	output(p2,sizeof(p2)/sizeof(p2[0])); //sizeof(p2)/sizeof(p2[0])取数组长度的另一种方法
	return 0;
}