|
插入排序的思想和我们打扑克摸牌的时候一样，从牌堆里一张一张摸起来的牌都是乱序的，我们会把摸起来的牌插入到左手中合适的位置，让左手中的牌时刻保持一个有序的状态。
那如果我们不是从牌堆里摸牌，而是左手里面初始化就是一堆乱牌呢？ 一样的道理，我们把牌往手的右边挪一挪，把手的左边空出一点位置来，然后在乱牌中抽一张出来，插入到左边，再抽一张出来，插入到左边，再抽一张，插入到左边，每次插入都插入到左边合适的位置，时刻保持左边的牌是有序的，直到右边的牌抽完，则排序完毕。
public static int[] sort(int[] arr) {
for (int i = 1; i < arr.length; ++i) {
int value = arr[i];
//插入的位置下标
int index = 0;
for (int j = i - 1; j >= 0; j--) {
//如果比插入数要大，后移一位
if (arr[j] > value) {
arr[j + 1] = arr[j];
} else {
index = j + 1;
break;
}
}
//插入数据
arr[index] = value;
}
return arr;
}
最好情况的时间复杂度是 O(n)，最坏情况的时间复杂度是 O(n2)
|