1）基本原理：
從第二項開始，依次與前面的元素比較，然後插入到合適的位置。
2）核心代碼：
public static void insertionSort(int[] a, int n) {
// a[0] 看做已排序
for (int i = 1; i < n; i++) {
int x = a[i]; // 待插入元素
int j=i-1; // 插入的位置
while (j >= 0 && a[j] > x) {
a[j+1] = a[j]; // 為待插入元素騰地
j--;
}
a[j+1] = x; // 特別注意是 j+1
}
}
3）特點：
平均時間複雜度是 O(n^2)，最佳情況是 O(n)，最差情況是 O(n^2)
空間複雜度 O(1)
穩定的排序算法
分享到:
閱讀更多 lucky小爺 的文章
