插入排序
插入排序类和大家玩的纸牌游戏有些类似，在发牌的过程的过程中用右手起的牌，总是和左手里的排进行比较，然后放在恰当的位置。这就是插入排序的思想。
以数组为例，其算法是：
（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)对于一般数量和大量数据效率非常的低
下面将会介绍希尔排序。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
