插入排序適合于部分有序序列和小規(guī)模的數據压彭。其平均時間復雜度為 O(N^2)，空間復雜度為 O(1)，并且為穩(wěn)定排序辕漂。
插入排序將待排序序列分為有序區(qū) (記為 S 區(qū))和無序區(qū)(記為 R 區(qū))浦妄。以從小到大的順序為例尼摹，每次從 R 區(qū)彈出一個元素 O，要將元素 O 插入到 S 區(qū)中恰當位置剂娄。從 S 區(qū)最右端開始蠢涝，依次比較 S 區(qū)元素與元素 O 的大小。如果元素O 比 S 區(qū)元素小阅懦，就將 S 區(qū)元素后移一位惠赫。如果元素 O 大于 S 區(qū)元素，就在該元素右邊一位插入元素 O故黑。
public static void insertionSort(int[] x) {
int N = x.length;
for (int i = 1; i < N; ++i) {
int value = x[i];
int j = i - 1;
for (; j >= 0; --j) {
if (x[j] > value) {
x[j + 1] = x[j];
} else {
break;
}
}
x[j + 1] = value;
}
}
演示：
public static void main(String[] args) {
int[] b = {3, 12, 17, 2, 19, 34, 91};
insertionSort(b);
for (int value: b)
System.out.printf("%d ", value);
}
輸出：2 3 12 17 19 34 91
