核心代码
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到达数组的右端时排序就完成了，其实就是如同拿到一副牌，理牌的过程，但每次只能一张一张来
- 插入排序对于部分有序的数组十分高效，也很适合小规模数组
网友评论