//插入排序

//C++

#include <iostream>

using namespace std;

void main()

{

    int a[6]={5,2,4,6,1,3};//定义一个未排好序的数组

    int i,j,key;

    for(i=0;i<6;i++)//输出排序前的序列

        printf("%3d",a[i]);

    for(j=1;j<6;j++)

    {

      key=a[j];

      i=j-1;

      while(i>=0&&a[i]>key)

      {

          a[i+1]=a[i];

          i=i-1;

      }

          a[i+1]=key;

    }

    cout<<endl;    

     for(i=0;i<6;i++)//输出排序后的序列

        printf("%3d",a[i]);

    cout<<endl;

}

//归并排序

//C++代码

#include <iostream>

using namespace std;

void mergearray(int a[],int first,int mid,int last,int temp[])// 将两个序列合成一个序列

{

int i,j,k,m,n;

i=first; j=mid+1;

m=mid; n=last;

k=0;

while(i<=m&&j<=n)

{

if(a[i]<=a[j])

temp[k++]=a[i++];

else

    temp[k++]=a[j++];

}

while(i<=m)

temp[k++]=a[i++];

while(j<=n)

    temp[k++]=a[j++];

for(i=0;i<k;i++)

a[first+i]=temp[i];

}

void mergesort(int a[],int first,int last,int temp[])//将一个数列递归分成两份

{

if(first<last)

{

      int mid=(first+last)/2;

  mergesort(a,first,mid,temp);

  mergesort(a,mid+1,last,temp);

  mergearray(a,first,mid,last,temp);

}    

}

void Mergesort(int a[],int n)//调用归并函数

{

int *p=new int[n];

mergesort(a,0,n-1,p);

    delete[] p;

}

void main()

{

int i;

int a[6]={6,5,4,3,2,1};

for(i=0;i<6;i++)//输出初始数列

 cout<<a[i]<<" ";

cout<<endl;

      Mergesort(a,6);

    for(i=0;i<6;i++)//输出排序后序列

  cout<<a[i]<<" ";

cout<<endl;

}

注释：归并排序算法是优于插入排序的算法，当排序的数据越多它的优势越明显。掌握一种更加高级的数据算法对于一个好的程序员来说非常重要。

插入排序和归并排序