排序演算法 (2) - Insertion sort
用兩個迴圈來實現，程式複雜度 O( n^2 )
空間複雜度僅需額外一個temp來作搬移的動作因此為 O( 1 )
(1) 第一個元素開始，在已經排序序列中從後向前檢查
(2) 若新元素大於序列元素，將新元素移到下一位置比對
(3) 重複直到已排序元素小於或者等於新元素的位置
(4) 將新元素插入
void InsertionSort(int *arr, int len)
{
int i, j;
int temp;
for (i = 1; i < len; ++i)
{
temp = arr[i]; //將第i個元素複製到temp做插入排序的動作
j = i - 1; //當次最後一個為i元素，由後向前做排序(i-1 to 0)
for (; j >= 0 && arr[j] > temp; --j) //從後向前做比較
{
arr[j + 1] = arr[j]; //將較大的元素通通向右方做shift的動作
}
arr[j + 1] = temp; //找到位置後插入
}
}