各式排序算法及其c语言实现

#include<iostream>
#include<vector>
using namespace std;

template <class T>
class Sort{
private:
	vector<T> arrayT;
	vector<T> temp;
public:
	Sort(){}
	Sort(vector<T> arr){
		arrayT=arr;
		temp=arr;
	}
	bool compare(T a,T b,bool arise){
		if(arise)
			return (a>b);
		else
			return !(a>b);
	}
	void swap(int i,int j){
		T temp=arrayT[i];
		arrayT[i]=arrayT[j];
		arrayT[j]=temp;
	}
	void print(){
		for(int i=0;i<arrayT.size();i++)
			cout<<arrayT[i]<<" ";
		cout<<endl;
	}
	int getSize(){return arrayT.size();}
	void bubbleSort(bool arise);//冒泡排序
	void insertSort(bool arise);//插入排序
	void quickSort(bool arise,int low,int high);//快速排序 注意这里的high指的是最后一个元素的位置坐标
	void adjustHeap(int i,int length,bool arise);//建堆
	void HeapSort(bool arise);//堆排序
	void MergeSort(int start,int end,bool arise);//归并排序
	void Merge(int start,int mid,int end,bool arise);//归并
	void ShellSort(bool arise);//希尔排序
};

//这里加入冒泡排序部分代码
//这里加入插入排序部分代码

int main(){
	int a[10]={1,3,5,7,9,2,4,6,8,0};
	vector<int> b(a, a+10);
	Sort<int> sortb(b);
	sortb.print();
	sortb.bubbleSort(true);
	sortb.print();
	for(int i=0;i<b.size();i++)
			cout<<b[i]<<" ";
		cout<<endl;
}

template<class T>
void Sort<T>::bubbleSort(bool arise){
	int n=arrayT.size();
	for(int i=0;i<n-1;i++)
		for(int j=0;j<n-i-1;j++)
			if(compare(arrayT[j],arrayT[j+1],arise))
				swap(j,j+1);
}

template<class T>
void Sort<T>::insertSort(bool arise){
	int n=arrayT.size();
	vector<T>::iterator it=arrayT.begin(),in;
	for(int it=1;it<n;it++){
		int flag=0;
		for(in=arrayT.begin();in!=arrayT.begin()+it;in++){
			if(compare(*in,arrayT[it],arise)){
			//找到第一个不满足比较条件的进行插入，这里外循环使用index,内循环使用迭代器与vector的结构有关
			//若外循环也使用迭代器，则会出现bug
			//原因是，在删除元素之后，vector的元素会重构，所有在erase后的元素所在的位置都会改变，所以迭代器指的位置不再是原来的位置，也就形成了空引用
				T temp=arrayT[it];
				arrayT.erase(arrayT.begin()+it);
				arrayT.insert(in,1,temp);
				break;
			}
		}
	}
}

template<class T>
void Sort<T>::quickSort(bool arise,int low,int high){
	if(low>=high){
		return;
	}
	int i=low;
	int j=high;
	T temp=arrayT[i];
	while(i<j){
		while(i<j&&compare(arrayT[j],temp,arise))j--;
		arrayT[i]=arrayT[j];
		while(i<j&&compare(temp,arrayT[i],arise))i++;
		arrayT[j]=arrayT[i];
	}
	arrayT[i]=temp;
	quickSort(arise,low,i-1);
	quickSort(arise,i+1,high);
}

template<class T>
void Sort<T>::adjustHeap(int i,int length,bool arise){
	T temp=arrayT[i];
	for(int k=i*2+1;k<length;k=2*k+1){
		if(k+1<length && compare(arrayT[k+1],arrayT[k],arise))k++;
		if(compare(arrayT[k],temp,arise)){
			arrayT[i]=arrayT[k];
			i=k;
		}else
			break;
	}
	arrayT[i]=temp;
}
template<class T>
void Sort<T>::HeapSort(bool arise){
	for(int i=arrayT.size()/2-1;i>=0;i--)
		adjustHeap(i,arrayT.size(),arise);
	for(int j=arrayT.size()-1;j>0;j--){
		swap(0,j);
		adjustHeap(0,j,arise);
	}
}

template<class T>
void Sort<T>::Merge(int start,int mid,int end,bool arise){
	int i=start,j=mid+1,k=start;
	while(i!=mid+1&&j!=end+1){
		if(compare(arrayT[i],arrayT[j],arise))
			temp[k++]=arrayT[j++];
		else
			temp[k++]=arrayT[i++];
	}
	while(i!=mid+1)
		temp[k++]=arrayT[i++];
	while(j!=end+1)
		temp[k++]=arrayT[j++];
	for(i=start;i<=end;i++)
		arrayT[i]=temp[i];
}

template<class T>
void Sort<T>::MergeSort(int start,int end,bool arise){
	int mid;
	if(start<end){
		mid=(start+end)/2;
		MergeSort(start,mid,arise);
		MergeSort(mid+1,end,arise);
		Merge(start,mid,end,arise);
	}
}

template<class T>
void Sort<T>::ShellSort(bool arise){
	int len=arrayT.size();
	for(int div=len/2;div>=1;div=div/2)
		for(int i=0;i<=div;i++)
			for(int j=i;j<len-div;j+=div)
				for(int k=j;k<len;k+=div)
					if(compare(arrayT[j],arrayT[k],arise))
						swap(j,k);
}