直接插入排序（模板）.cpp

一份学习c++必不可少的程序

#include<iostream.h>
template<typename T>struct Node{
	T key;
};
template<typename T,int size>class Orderlist{
	int m;
	int last;
	Node<T>slist[size];
	public:
		Orderlist(){last=-1;m=size;}
		void InsertSort();
		bool Insert(Node<T>&elem,int i);
		void print();
};
template<typename T,int size>bool Orderlist<T,size>::Insert(Node<T>&elem,int i){
	if(i<0||i>last+1||last==m-1)return false;
	else{
		for(int j=last;j>i;j--)slist[j]=slist[j-1];
		slist[i]=elem;
		last++;
		return true;
	}
}
template<typename T,int size>void Orderlist<T,size>::print(){
	int i;
	for(i=0;i<last;i++){
		cout<<slist[i].key<<'\t';
		if(i%8==7)cout<<endl;
	}
	cout<<endl;
}
/*template<typename T,int size>void Orderlist<T,size>::InsertSort(){//升序直接插入排序
	Node<T>temp;
	int i,j;
    for(i=0;i<last;i++){
		temp=slist[i];
		j=i;
		while(j>0&&temp.key<slist[j-1].key){
			slist[j]=slist[j-1];
			j--;
		}
		slist[i]=temp;
	}
}*/
template<typename T,int size>void Orderlist<T,size>::InsertSort(){//对半插入排序
	Node<T>temp;
	int low,high,mid,i;
    for(i=0;i<last;i++){
		temp=slist[i];
		low=0;
		high=i-1;
		while(low<=high){
		mid=(low+high)/2;
		if(temp.key<slist[mid].key)high=mid-1;
		else low=mid+1;
		}
		for(int j=i-1;j>=low;j--)slist[j+1]=slist[j];
		slist[low]=temp;
	}
}
void main(){
	const int  h=19;
	int i;
	Orderlist<int,100>ordlist;
	int a[h]={52,32,69,57,41,12,32,21,56,98,58,25,21,31,41,64,34,16,91};
	Node<int>n[h];
	for(i=0;i<h;i++)n[i].key=a[i];
	for(i=0;i<h;i++)ordlist.Insert(n[i],i);
	cout<<"未排序表："<<endl;
	ordlist.print();
	ordlist.InsertSort();
    cout<<"已排序表："<<endl;
	ordlist.print();
}