排序是一个很有趣的问题，我觉得大家可以思考一下，为什么大多数算法书籍都会把排序放在很靠前的位置呢。我觉得，是因为排序可以引出很多和算法有关的知识。
当你开始接触排序算法时，（只要不是课本）一般第一个和第二个算法总是插入、选择排序。为什么呢，因为他们的时间复杂度很好分析。
那我们先来看看插入排序。
插入排序（InsertionSort）之所以得名，就是因为该算法每次把一个元素插入此元素之前的某一个合适位置。记得CLRS还用了扑克牌整理的例子，感觉好可爱啊。
于是，我们就会这样描述这个算法：假设想要排出一个增序序列，对第2个元素做Insert，元素2是否小于第1个，是的话，插入到第一个之前，否则不变，排好序；对第3个元素Insert，是否小于第2个，是→插入第2个之前。是否小于第1个，是→插入第1个之前，排好序；······；对最后一个元素做Insert，排好序。
所以，插入排序就有一个特点：在对第n个元素做插入算法时，其前n-1个元素已经排好了序。那么当我们做Insert时，就需要注意一点：当我们的目标元素不满足条件时，我们的判断就应该立刻终止，不应该继续做无用功。
那么，我们来用c语言实现一下该算法：
void InsertionSort( ElementType A[ ], int N) //ElementType是指元素的类型，比如int，float等；N是元素总个数
{
int i, j;
ElementType tmp; //使用tmp保存执行插入元素的值，当然也可以不用
for( i = 1; i < N; ++i )
{
tmp = A[ i ];
for( j = i; j > 0 && tmp < A[ j - 1 ]; --j ) //比较tmp之前所有值和它的大小
A[ j - 1 ] = A[ j ]; //把符合条件的（就是比tmp大的）向后移动一位
A[ j ] = tmp; //把tmp的值移动到停止的那一位上
}
}
在有注释的情况下其实很好阅读了，那么我们分析几个功能，首先，
tmp < A[ j - 1 ]
这里因为我们把控制比较的元素设为 j ， j 因为是从i开始的，故我们一开始就让 tmp 和 A[j-1] 比较，若是符合比较的条件，则把 A[j-1] 后移一位，然后 j 自减1。因为tmp始终是和 A[j-1] 比较，也就是说，最后 tmp 所放置的位置是不满足条件的 A[j-1] 的前一个位置。这样就很巧妙了。
BTW，其实也可以让 j 一开始就等于 i-1，那么，代码要怎样改写呢，请大家自己写一下，因为很方便检测，我就不说了。（hint，可以看看CLRS，此书就是用的这种逻辑，但是在实现的时候有个问题，就是 j 有可能会减到-1，如果用size_t控制j的类型的话，会出错~）
现在让我们来聊2个c/c++的语法问题。第一个是for循环。我想大家都知道，如果for循环不满足条件，是会结束的吧。那么也请大家不要忘记了，
for( j = i; j > 0 && tmp < A[ j - 1 ]; --j )
在tmp < A[ j - 1 ]不满足时，循环也会立刻结束，千万别臆想成：直到j>0不满足了才stop。为什么要说这个呢，因为在选择排序中，我们需要程序一直判断，而不是不满足就立刻停下。
第2个是这个ElementType。因为我们不知道我们所求的数组是什么类型，所以我们将其称作“元素类型”。在c++的实现中，为了避免这种很“伪代码”的写法，我们有2种做法，一是函数重载。比如我们想要算法满足int，double类型的计算，则可以有如下声明：
void InsertSort( int A[ ], int N );
void InsertSort( double A[ ], int N );
重载需要注意的问题是，不允许重载只有返回类型不同的函数。
第二个做法，就是泛型了。泛型用起来是有点难的，和java相比。那么我们简单了解下本问题的泛型好了。
c++泛型函数模板的方法：
template <typename T> void InsertSort( T A[ ], int N )
{
...
T tmp = A[ i ]; //或者 auto tmp = A [ i ];
...
}
然后直接调用就可以了。因为编译器会帮你自动实例化.
然后简单说下其时间复杂度。如果序列是顺序的，则内部循环每次只执行一次，是T(1)的，所以O()=T(n)*T(1)=O(n)；若最差（反序），则内部分别需要比较和移动1，2，···，n-1次，所以共O(n2)次；对于平均情况，假设一半顺序一半逆序，则依然是O(n2)。
真是没有想到，一个插入排序就能写这么多······本来想把插入，选择，希尔排序一起写了，那就下次再写吧~
