算法导论笔记 -- Step 1 [插入排序]

**转载请注明**

    一个开头总要说些开场白，‘闲来无事’之类的，好吧，最近因为在了解数据库索引机制，无意发现了‘红黑树’，看了半天发现算法机制已经忘得差不多了，重补《算法导论》，随手记一些代码，希望有机会的时候拿出来能够再快速补脑~

    不知道该算是‘翻译’还是‘原创’，总之顺序和插图都是来自于《Introduction of Algorithms》(3rd)，算是笔记吧。

Getting Started:

插入排序（Insertion Sorp)
    原理：

    * 循环从2~6， 黑色数字依次跟前一个比，如果比前一位小就移位，直到最终结束或者遇到更小的。
    * 说白了就是抓牌，每抓一张插进去，大的都往后移

C++ 代码：
    

[myang@mnsdev13:~/dev/cpp]$ cat insertion_sort.cpp
#include <iostream>

using namespace std;

void INSERTION_SORT( int*, int );

int main(){
    int a[] = {5,2,4,6,1,3};

    INSERTION_SORT(a, sizeof(a)/sizeof(int));

    for (int i = 0; i < sizeof(a)/sizeof(int); i++){
        cout << a[i] << endl;
    }
    return 0;
}

void INSERTION_SORT( int* array, int len ){
    // 从第二个到最后
    for (int j = 1; j < len; j++){
        int i = j - 1;   // i 是黑色前一个数
        int k = array[j]; // 把黑色先存下来

        while ( i >= 0 && array[i] > k ){ //如果还有数字，而且还大于此轮比较的数字
            array[i+1] = array[i];
            i--; // 看来k不能放在这 还得比
        }
        array[i+1] = k; // 比完了，比i大或者i是-1了。存在i后边或者0位置
    }
}

运行结果：
    

空间复杂度：
    O（1）

时间复杂度：
    O（n^2)