排序（模版+代码）

插入排序：

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外，而第二部分就只包含这一个元素。在第一部分排序后，再把这个最后元素插入到此刻已是有序的第一部分里的位置。

//Insertion_sort
#include<iostream>
#include<cstdlib>
using namespace std;
int main()
{
	int a[10],i;
	for(i=1;i<10;i++)
	  a[i]=1+rand()%100;//随机生成一些整数
	  //Insert_sort
	  for(i=2;i<10;i++)
	  {
	  	// 将a[i] insert the sequence a[i-1]....a[1]
		  int key=a[i];
		  int j=i-1;
		  while(j>0&&a[j]>key)
		  {
		  	a[j+1]=a[j];
		  	j--;
		  } 
		  a[j+1]=key;
	  } 
	  //printf the result
	  for(i=1;i<10;i++)
	  {
	  	cout<<a[i]<<" ";
	  } 
	  cout<<endl;
	  return 0;
}

               每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

//Selection_insert
#include<iostream>
#include<cstdlib>
using namespace std;
int main()
{
	int a[10],i,j,key,temp,k;
	//随机生成9个数
	for(i=1;i<=9;i++)
	{
		a[i]=1+rand()%100;
	} 
    //Selection_insert
	for(i=1;i<=9;i++)
	{
		//slect the smallest number from the sequence
		 key=a[i]; 
		for(j=i+1;j<=9;j++)
		{
			if(a[j]<key)
			{
				key=a[j];
				k=j;
			}
		} 
		//change
		if(key<a[i])
		{
			temp=a[i];
             a[i]=key;
             a[k]=temp;
		}
	} 
	for(i=1;i<9;i++)
	cout<<a[i]<<" ";
	cout<<endl;
	return 0;
}

//Merge_sort
#include<iostream>
#include<cstdlib>
const int maxnum=999999;
using namespace std;
int a[50];
void merge(int *a,int p,int q,int r)
{
	int m=q-p+1;
	int n=r-q;
	int left[100],right[100];
	int i,j,k;
	for(i=1;i<=m;i++)
	{
		left[i]=a[i+p-1];
	}
	for(j=1;j<=n;j++)
	{
		right[j]=a[j+q];
	}
	left[m+1]=maxnum;
	right[n+1]=maxnum;
	i=j=1;
	k=p;
	while(k<=r)
	{
		if(left[i]<=right[j])
		{
			a[k++]=left[i++];
		}
		else 
		    a[k++]=right[j++];
	}
}
void merge_sort(int *a,int p,int q)
{
	if(p<q)
	{
	merge_sort(a,p,(p+q)/2);
	merge_sort(a,(p+q)/2+1,q);
	merge(a,p,(p+q)/2,q);
    }
}
int main()
{
	int i,j;
	for(i=1;i<=49;i++)
	{
		a[i]=1+rand()%99;
	}
	merge_sort(a,1,49);
	for(i=1;i<=49;i++)
	cout<<a[i]<<" ";
	cout<<endl;
	return 0;
} 

//HEAP_SORT
#include<iostream>
#include<cstdlib>
using namespace std;
int maxv=49,a[50];
void Max_Heapify(int *a,int i)
{
	int l=i*2,r=i*2+1,largest;
	if(l<=maxv&&a[l]>a[i])
	    largest=l;
    else 
        largest=i;
    if(r<=maxv&&a[r]>a[largest])
       largest=r;
       if(largest!=i)
       {
       	int temp=a[i];
       	a[i]=a[largest];
       	a[largest]=temp;
       	Max_Heapify(a,largest);
       }
}
void Build_Max_Heap(int *a)
{
	int i;
	for(i=maxv/2;i>=1;i--)
	 Max_Heapify(a,i);
} 
void Heap_Sort(int *a)
{
	for(int i=maxv;i>=2;i--)
	{
	    int temp=a[1];
	    a[1]=a[i];
	    a[i]=temp;
	    maxv=maxv-1;
	    Max_Heapify(a,1);
	}
}
int main()
{
	int i,j;
	for(i=1;i<50;i++)
	a[i]=1+rand()%99;
	Build_Max_Heap(a);
	Heap_Sort(a);
	for(i=1;i<=49;i++)
	cout<<a[i]<<" ";
	cout<<endl;
	return 0;
}
 

//Counting_Sort
#include<iostream>
using namespace std;
int main()
{
	int a[9]={0,2,5,3,0,2,3,0,3};
	int c[6];
	int i;
	int b[9];
	for(i=0;i<=5;i++)
	c[i]=0;
	for(i=1;i<=8;i++)
	c[a[i]]=c[a[i]]+1;
	for(i=1;i<=5;i++)
	c[i]=c[i-1]+c[i];
	for(i=8;i>=1;i--)
	{
		b[c[a[i]]]=a[i];
		c[a[i]]--;
	}
	for(i=1;i<=8;i++)
	cout<<b[i]<<" ";
	cout<<endl; 
	return 0;
}