算法学习笔记（二）：插入排序

算法思想：A[i]插入到已排序好的A[0,1,2,...i-1]的过程为将A[i]与已排序好的元素比较，找到其应插入的位置，将其后的元素后移一位。

循环这一过程即可完成排序

⒈ 从第一个元素开始，该元素可以认为已经被排序

⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描

⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置

⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

⒌ 将新元素插入到下一位置中

⒍ 重复步骤2~5

算法复杂度：O（n²）

算法改进：可以将查找位置部分改成二分查找，从而运行时间可以到nlgn

伪代码

INSERTION-SORT(A)

1forj=2tolength[A]

2dokey=A[j]

3 //InsertA[j] into the sorted sequenceA[1..j-1].

4 i=j-1

5 whilei>0 andA[i] >key

6 doA[i+1] =A[i]

7 i=i-1

8 A[i+1] =key

代码实现：

void insert_sort(int array[],int n)
{

    int temp;
    for (int j = 1; j < n;++j)
    {
        temp = array[j];
        int i = j-1;
        while (i>=0&&array[i]>temp)
        {
            array[i+1] = array[i];
            --i;
        }

        array[i+1] = temp;

    }
}