第1天-插入排序

算法说明

插入排序是算法导论一书中第一个算法，在书中举了一个非常恰当的扑克牌例子来说明插入排序的算法原理：
Input: {5 2 4 6 1 3}。
首先拿起第一张牌, 手上有 {5}。
拿起第二张牌 2, 把 2 insert 到手上的牌 {5}, 得到 {2 5}。
拿起第三张牌 4, 把 4 insert 到手上的牌 {2 5}, 得到 {2 4 5}。
以此类推。

算法复杂度

时间复杂度 O(n²)
空间复杂度 O(1)

算法图示

insertion-sort Insertion-sort gif

示例代码(C++)

#include <iostream>

int main() {
    int ary[6] = {5,2,4,7,1,3};
    int key,i;
    for(int j = 1; j < 6; j++) {
        key = ary[j];
        i = j-1;
        while(i >= 0 && ary[i] > key) {
            ary[i+1] = ary[i];
            i = i - 1;
        }
        ary[i+1] = key;
    }
    for(int j = 0; j < 6; j++)
        std::cout << ary[j] ;
    return 0;
}

源码资源

源码链接