插入排序算法笔记

插入排序：
1、最简单的排序算法。
2、在增量排序中有很高的效率，比如已经存在成绩排序，要插入一个新的成绩并且排序。
3、不需要额外的存储空间（属于内部排序）。
4、时间复杂度为O(n^2)。
首先，定义数组的形式为：num[MAX + 1] // MAX是已经定义的常量，num[ 0 ]闲置或者作为哨兵单元
算法描述：
<pre><code>
//-------------------------------------
//参数：1.排序数组首地址 2.数组长度
void Insert_Sord(int num[], int max)
{
for(int i=2; i <= max; ++i)
{
if(num[i] < num[i-1]) //待排序中的第一个元素 < 已排序中的最后一个元素
{
num[0] = num[i]; //将要插入的元素赋值给哨兵num[0]
num[i] = num[i-1]; //已排序数组后移，即长度+1
for(int j=i-2; num[0]<num[j]; --j)//从已排序中倒数第二个开始比较
num[j+1] = num[j]; //已排序中，比哨兵大的元素往后移
num[j+1] = num[0]; //将哨兵元素值插入
}
}
}
//=====================================
</code></pre>