核心代碼
public static void sort(Comparable[] a) {
//將a[]按升序排列
int N = a.length;
for (int i = 1; i < N; i++) {
//將a[i]刺插入到a[i-1]褐耳、a[i-2]······之中
for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
exch(a, j, j - 1);
}
}
}
Tips:
- 插入排序的運行時間是平方級別的措嵌，不需要額外的存儲空間
- 插入排序的核心思想：對于1到N-1之前的每一個i,將a[i]與a[0]到a[i-1]中比它小的所有元素一次有序的交換累舷，在索引i由左到右變化的過程中派继，它左側的元素總是有序的，所以i到達數(shù)組的右端時排序就完成了，其實就是如同拿到一副牌，理牌的過程框弛，但每次只能一張一張來
- 插入排序?qū)τ诓糠钟行虻臄?shù)組十分高效，也很適合小規(guī)模數(shù)組
