排序算法---插入排序

基本思想：

从目标数组中选出一个元素与已经排好序的数组元素逐个比较，找到合适的位置插入。

插入排序的C语言实现：

int insert_sort(int array[], int lenth)
{
    int i = 0, j = 0;
    int temp = 0;

    for (i = 0; i < lenth; i++) {
        temp = array[i];
        for (j = i; (j > 0) && array[j] > temp.key; j--) {
            array[j+1] = array[j];
        }
        array[j+1] = temp;
    }

    return 0;
}

代码分析：

         从下标0的数组元素开始，用temp变量保存这个元素，然后用temp与已排好顺序的数组逐个比较(从目的数组的后面往前逐个比较)要将已排好序的数组满中足条件的元素向后移动，直到不满足条件时j+1即为要插入的位置。

注意:

        1.因为上述代码是在原数组基础上进行移动的，所以要用temp值保存准备要插入的元素。

        2.从下标为0的元素开始，在此之前没有已经排好的序列，所以跟据j>0的条件直接将逐个元素放到所谓的“排好序”的数组的首位（其实就是原数组的0下标位置）。

时间复杂度：

        插入排序的时间复杂度取决于每个要排序的元素之前有多少个元素是比它大的(以从小到大排来说)。这个值越大，时间复杂度越高，O(n*移动次数)。

        如果要排序的数组是倒序的，那么时间复杂度是O(n2),实际上就是冒泡排序了。

以上是我个人对插入排序的一点理解，不是很专业，有问题的话还望各位斧正。