Insertion Sort (插入排序法)

概念 - 教學影片

Insertion Sort之舞 影片

將要排序的對象分作兩部份，一個是已排序的，一個是未排序的。

每次從後端未排序部份取得最前端的值，然後插入前端已排序部份的適當位置。

作法

1. 假設第一個元素已經排序
2. 取出下一個元素（未排序元素中第一個），從已經排序的元素序列中由後往前掃
3. 如果該元素（已排序）大於新元素，將該元素一到下一個位置
4. 重複步驟3, 直到找到已排序的元素小於或者等於新元素的位置
5. 將新元素插到該位置後面
6. 重複步驟2-5 直到全部排完

Pseudo Code

const int N = 5;
int students[N] = {4,3,5,1,7};


for ( int i = 1 ; i < N ; i++ ){

    int newVal = students[i];

    int insertPosition = i-1;

    while ( insertPosition >= 0 ){
        if ( newVal >= students[insertPosition]  ) 
            break;

        students[insertPosition+1] = students[insertPosition];
        insertPosition--;
    }

    students[insertPosition+1] = newVal;

}