InsertionSort（插入排序）原理及C++代碼實現

插入排序是最常用的排序之一。

在輸入規模較小的時候，插入排序的性能較好。

最好情況下插入排序的時間複雜度是O(n),平均情況則為O(n2)。

插入排序是穩定的排序演算法之一。

基本思路為從第二個元素開始，依次插入前面已經排好序的序列，利用迴圈不變式很容易理解。

代碼如下：（僅供參考）

 1 void InsertionSort(int * const begin, int * const end) {
 2     int i, j;
 3     int key;
 4     for (i = 1; i < end - begin; ++i) {
 5         key = *(begin + i);
 6         for (j = i - 1; j >= 0 && (*(begin + j) > key); --j) {
 7             *(begin + j + 1) = *(begin + j);
 8         }
 9         *(begin + j + 1) = key;
10     }
11 }

註：指針需要支持隨機訪問