- 算法思想
- 算法实现
- 算法效率
- 比较次数
- 时间复杂度(和比较次数有关)
- 空间复杂度
- 和选择排序比较
将初始数据分为 有序部分 和 无序部分，每一步 将一个无序部分的数据 插入到 前面已经排好序的 有序部分中，直到插完所有元素为止
插入排序的步骤如下：每次从无序部分中取出一个元素，与 有序部分中的元素 从后向前 依次进行比较，并找到合适的位置，将该元素插到有序组当中
算法实现 public static void insertSort(int[] nums) {
for (int i = 0; i < nums.length; i++) {
// 从后向前比较
for (int j = i; j > 0; j--) {
if (nums[j - 1] > nums[j]) {
int tmp = nums[j];
nums[j] = nums[j - 1];
nums[j - 1] = tmp;
}
}
}
}
算法效率
比较次数
比较的总次数 是 交换的次数 加上一个 额外的项，该项为 N 减去 被插入的元素，正好是已知的 最小元素的次数
在最坏情况下（逆序数组），这一项相对于总数可以忽略不计
在最好情况下（数组已经有序），这一项等于N-1
当 待排序序列 是 有序时，是最优的情况，只需 当前数 跟 前一个数 比较一下就可以了，这时一共需要比较N-1次，时间复杂度为O(N)
最坏的情况是 待排序数组 是 逆序的，此时需要比较次数最多，总次数记为：1+2+3+…+N-1，时间复杂度为O( N 2 N^2 N2)
平均来说，array[1…j-1]中的一半元素小于array[j]，一半元素大于array[j]。插入排序在平均情况运行时间与最坏情况运行时间一样，是O( N 2 N^2 N2)
空间复杂度O(1)
和选择排序比较与选择排序一样，当前索引左边的所有元素都是有序的，但它们的最终位置还不确定，为了给更小的元素腾出空间，它们可能会被移动
但是当索引到达数组的右端时，数组排序就完成了
和选择排序不同的是，插入排序所需的时间 取决于 输入中元素的初始顺序
例如，对一个很大且其中的元素已经有序（或接近有序）的数组 进行排序 将会比 对随机顺序的数组或是逆序数组进行排序要快得多
插入排序 对于实际应用中 常见的 某些类型的非随机数组很有效
要考虑的更一般的情况 是 部分有序的数组
倒置指的是 数组中的两个顺序颠倒的元素
比如 E X A M P L E 中有 11 对倒置：E-A、X-A、X-M、X-P、X-L、X-E、M-L、M-E、P-L、P-E 以及 L-E
如果 数组中 倒置的数量 小于 数组大小的某个倍数，那么说这个数组 是 部分有序的
下面是几种典型的部分有序的数组：
- 数组中每个元素距离它的最终位置都不远
- 一个有序的大数组 接一个 小数组
- 数组中只有几个元素的位置不正确
插入排序对这样的数组很有效，而选择排序则不然(因为要遍历所有元素之后找到最小的元素，所以耗费的次数更多)
事实上，当倒置的数量很少时，插入排序很可能比其他任何算法都要快
