fsort.cpp

多种排序算法实现

#include<vector>
#include<iostream.h>
using namespace std;
template<typename T>
void InsertionSort(vector<T>& v)
{
	int i,j,n=v.size();
	T target;
	for(i=1;i<n;i++)
	{
		j=i;
		target=v[i];
		while(j>0&&target<v[j-1])
		{
			v[j]=v[j-1];
			j--;
		}
		v[j]=target;
	}
}

template <typename T>
void BubbleSort(vector<T>& v)
{
	int n=v.size();
	T temp;
	for(int i=0;i<n-1;i++)
		for(int j=0;j<n-1-i;j++)
			if(v[j]>v[j+1])
			{
				temp=v[j];
				v[j]=v[j+1];
				v[j+1]=temp;
			}
}

template<typename T>
void ExchangeSort(vector<T>& v)
{
	int i,j,n=v.size();
	T temp;
	for(i=0;i<n-1;i++)
		for(j=i;j<n;j++)
			if(v[i]>v[j])
			{
				temp=v[i];
				v[i]=v[j];
				v[j]=temp;
			}
}



template <typename T>
void SelectionSort(vector<T>& v)
{
   // index of smallest item in each pass
	int smallIndex;
	// save the vector size in n
	int pass, j, n = v.size();
	T temp;

	// sort v[0]..v[n-2], and arr[n-1] is in place
	for (pass = 0; pass < n-1; pass++)
	{
		// start the scan at index pass; set smallIndex to pass
		smallIndex = pass;
		// j scans the sublist v[pass+1]..v[n-1]
      for (j = pass+1; j < n; j++)
         // update smallIndex if smaller element is found
         if (v[j] < v[smallIndex])
            smallIndex = j;
      // when finished, place smallest item in arr[pass]
      if (smallIndex != pass)
		{
			temp = v[pass];
			v[pass] = v[smallIndex];
			v[smallIndex] = temp;
		}
   }
}
void main()
{
	int n,t,y;
	double m;
	cout<<"请输入数组的长度n"<<'\n';
	cin>>n;
	vector<double> v(n);
	cout<<"请输入数组元素"<<'\n';
	for(int i=0;i<n;i++){
		cin>>m;
		v[i]=m;
	}
	while(t)
	{
		cout<<"Input the number of sortType:\n"
			<<"0-end\n"
			<<"1-SelectionSort\n "
			<<"2-InsertionSort\n "
			<<"3-BubbleSort\n "
			<<"4-ExchangeSort\n ";
		cin>>y;
		switch(y)
		{
		case 0:t=0;break;
		case 1:SelectionSort<double>(v);	break;
		case 2:InsertionSort<double>(v);	break;
		case 3:BubbleSort<double>(v);	break;
		case 4:ExchangeSort<double>(v);	break;
		default:t=1;break;		}
		if(t==0)cout<<"The program is end"<<'\n';
		else if(t==1)cout<<"the input is incorrect,please select from 1-4"<<'\n';
		else{
		for(int i=0;i<n;i++)
			cout<<v[i]<<"   ";
		}
		cout<<'\n';
	}

}