插入排序

插入排序类和大家玩的纸牌游戏有些类似，在发牌的过程的过程中用右手起的牌，总是和左手里的排进行比较，然后放在恰当的位置。这就是插入排序的思想。

以数组为例，其算法是：

（1）把数组里第一个数据放在a[0]的位置，然后从a[1]开始，以后的每一个数依次和它前面已经排好的数进行比较，然后放在合适的位置。

（2）a[1]可以放在两个位置一个是数组的头位置，一个是其现在的位置即a[1]

（3）从a[2]开始的数据，就有三种放法了，一个是数组的头位置，一个是其现在的位置，另一个是他前面已排好的数据的中间。

（4）若数据插入头和中间，从插入位置开始，它以后的数据位置依次往后挪动一个位置这就是插入排序的算法。

下面是插入排序实现的c++代码。

 C++代码

#include<iostream>

using namespace std;

void sort2(int inarray[],int insize)

{

 for(int i=1;i<insize;i++)

 {

  int element=inarray[i];

  int j=i-1;

  while(j>=0&&inarray[j]>element)

  {

    inarray[j+1]=inarray[j];

    j--;

   }

 inarray[j+1]=element;

 }

}

int main()

{

  int a[10]={9,6,3,8,5,2,7,4,1,0};

  sort2(a,10);

 for(int i=0;i<10;i++)

 cout<<a[i]<<endl;

 return 0;

}

算法复杂度  n^2 

优点：

（1）      易于实现

（2）      对于少量数据非常高效

（3）      运行时占用内存很少

（4）      算法稳定

缺点：

(1)对于一般数量和大量数据效率非常的低

下面将会介绍希尔排序。