同学说有更多细节的排序算法插入排序
这是排序算法学习的第三章「插入排序算法」，排序算法作为实用且面试常考的算法，虽然各大编程语言都有其相关的API实现。但是通过学习各种排序算法来训练编码能力，锻炼算法思维，入门算法~
目前为止，我们已经学习了
- 冒泡排序
- 选择排序
两者排序算法的优劣其实都差不太多，都是时间复杂度为O(N2)O(N^2)O(N2),空间复杂度为O(1)O(1)O(1)。最为不同的区别在于对于稳定性上：
- 冒泡排序能保证稳定性。
- 选择排序不能保证其稳定性。
今天我们就来学习第三种排序算法：插入排序
下面是各大排序算法的时间复杂度和空间复杂度，以及稳定性
| 排序算法 | 平均时间 | 最好时间 | 最坏时间 | 空间 | 稳定性* |
|---|---|---|---|---|---|
| 冒泡 | O(n2)O(n^2)O(n2) | O(n)O(n)O(n) | O(n2)O(n^2)O(n2) | O(1)O(1)O(1) | 稳定 |
| 选择 | O(n2)O(n^2)O(n2) | O(n2)O(n^2)O(n2) | O(n2)O(n^2)O(n2) | O(1)O(1)O(1) | 不稳定 |
| 插入 | O(n2)O(n^2)O(n2) | O(n)O(n)O(n) | O(n2)O(n^2)O(n2) | O(1)O(1)O(1) | 稳定 |
| 希尔 | O(nlogn)O(nlogn)O(nlogn) ~ O(n2)O(n^2)O(n2) | O(nlogn)O(nlogn)O(nlogn) | O(n2)O(n^2)O(n2) | O(1)O(1)O(1) | 不稳定 |
| 希尔 | O(nlog3n)O(nlog_3n)O(nlog3n) ~ O(n32)O(n^\frac{3}{2})O(n23) | O(nlog3n)O(nlog_3n)O(nlog3n) | O(n32)O(n^\frac{3}{2})O(n23) | O(1)O(1)O(1) | 不稳定 |
| 归并 | O(nlogn)O(nlogn)O(nlogn) | O(nlogn)O(nlogn)O(nlogn) | O(nlogn)O(nlogn)O(nlogn) | O(n)O(n)O(n) | 稳定 |
| 快速 | O(nlogn)O(nlogn)O(nlogn) | O(nlogn)O(nlogn)O(nlogn) | O(n2)O(n^2)O(n2) | O(logn)O(logn)O(logn) | 不稳定 |
| 堆 | O(nlogn)O(nlogn)O(nlogn) | O(nlogn)O(nlogn)O(nlogn) | O(nlogn)O(nlogn)O(nlogn) | O(1)O(1)O(1) | 不稳定 |
| 计数 | O(n+k)O(n + k)O(n+k) | O(n+k)O(n + k)O(n+k) | O(n+k)O(n + k)O(n+k) | O(n+k)O(n + k)O(n+k) | 稳定 |
| 基数 | O(d(n+k))O(d(n + k))O(d(n+k))kkk 为常数 | O(d(n+k))O(d(n + k))O(d(n+k))kkk 为常数 | O(d(n+k))O(d(n + k))O(d(n+k))kkk 为常数 | O(n+k)O(n + k)O(n+k) | 稳定 |
| 桶 | O(n)O(n)O(n) | O(n)O(n)O(n) | O(n2)O(n^2)O(n2) or O(nlogn)O(nlogn)O(nlogn) | O(n)O(n)O(n) | 稳定 |
算法描述
插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动 。——百度百科
对于一个待排序的数组（升序），从第二个元素开始（称为插入对象元素），比较它与之前的元素（称为比较对象元素，有序），当插入元素小于比较元素时，比较元素「后移」，继续往前比较，直到「大于等于」比较对象，此时将插入对象元素插入到该比较对象元素之后。重复这个过程直到最后一个元素作为对象完成插入操作。
根据描述，我们可以很自然的发现此排序的操作最主要的操作就是「插入」。选定一个元素与之前的元素进行比较当符合要求时进行插入操作。
稳定性
插入排序的核心操作就是与前面的元素进行比较，找到符合的位置进行插入。所以并不会改变过数组中的相等元素的相对位置。所以是保证其「稳定性」的。
代码实现
public static void insertSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) { // n - 1轮次执行
int target = arr[i], j = i - 1;
for (; j >= 0; j--) {
//元素往后移
if (target < arr[j]) arr[j + 1] = arr[j];
//此时target要大于等于arr[j] 说明target要插入j+1位置
else break;
}
// j变动表示发生了移动，此时的插入对象数字 ≥ j位置的数字，故插入位置为j + 1
if (j != i - 1) arr[j + 1] = target;
}
}
代码优化
通过算法描述我们可以知道插入排序算法的核心（升序）：在一个已经「有序」的数组中，找到「插入对象元素」的位置。其实这个过程是可以使用一个算法来优化的。它就是「二分查找」，找到数组中「大于等于」插入元素的位置，就是要插入的位置。（这里就不细讲二分了，挖坑）。找到要插入的位置之后，把前面的元素都向后移动，然后进行插入即可。
同时还存在当前「插入对象」大于前一个对象时，因为前面的数组已经有序，所以当前元素是不需要排序了。可以跳过。
public static void insertSortOpt(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
//如果当前插入对象大于前一个对象，无需插入（因为[0,i-1]已经有序 剪枝）
if (arr[i - 1] <= arr[i]) continue;
int target = arr[i];
int left = 0, right = i - 1;
//二分查找 「大于等于」
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
//往后移动「left=right+1」（与上文j初始位置不同）
for (int j = i; j > left; --j) arr[j] = arr[j - 1];
//插入
arr[left] = target;
}
}
对于大小相同的两个数字，简单插入和折半插入均使得后来的数字靠右放置 （因为条件是 ≥ ），因此不会改变其相对位置。
时间空间复杂度
时间复杂度：两层 forforfor 循环，外层总轮次为 n−1n - 1n−1 轮 ( n = arr.length ) ，当原数组逆序时，移动次数为 n∗(n−1)/2n*(n - 1) / 2n∗(n−1)/2 次，最坏时间复杂度为 O(n2)O(n^2)O(n2)，平均时间复杂度同为 O(n2)O(n^2)O(n2)。当原数组已基本有序时，接近线性复杂度 O(n)O(n)O(n)。例如原数组已完全排序，则算法只需比较 n - 1 次。
※ 折半插入总的查找(比较)次数虽为 O(nlogn)O(nlogn)O(nlogn)，但平均移动 (每轮移动一半的数字) 次数仍是 O(n2)O(n^2)O(n2)。
空间复杂度：算法中只有常数项变量，O(1)O(1)O(1)。
到此为止，插入排序就学习完成了。它的时间复杂度还是为O(N2)O(N^2)O(N2)，空间复杂度为O(1)O(1)O(1)。和冒泡排序一样是能够保证其「稳定性」的，同时算法实现上比其两种难一点，大家要多多编写，不懂的可以用ide进行debug，或者评论区提问哦~~
认为本文写的不错的话，请来一个点赞，收藏，关注吧~~~~
