插入排序¶
一、算法描述¶
1.1 核心思想¶
- 数据分为已排序区间和未排序区间
- 插入都是从未排序区间取出元素，插入到已排序区间合适的位置中
- 插入已排序区间时，同时要保证已排序区间的有序性
1.2 细节解释¶
比如说，数组 [2, 7, 1, 4, 3, 6, 5]。
首先分成未排序和已排序区间，第 1 个值无需排序，默认属于已排序区间：
已排序 未排序
___ ___ ___ ___ ___ ___ ___
| 2 | | 7 | 1 | 4 | 3 | 6 | 5 |
此时从未排序区间中取一个值 7，插入到已排序区间：
因为 7 > 2，所以 7 直接插入到 2 后面：
已排序 未排序
___ ___ ___ ___ ___ ___ ___
| 2 | 7 | | 1 | 4 | 3 | 6 | 5 |
继续从未排序区间取值 1，此时 1 < 7、1 < 2，所以插入到 2 前面：
已排序 未排序
___ ___ ___ ___ ___ ___ ___
| 1 | 2 | 7 | | 4 | 3 | 6 | 5 |
以此类推，后面每一步的结果如下：
插入 4：
已排序 未排序
___ ___ ___ ___ ___ ___ ___
| 1 | 2 | 4 | 7 | | 3 | 6 | 5 |
插入 3：
已排序 未排序
___ ___ ___ ___ ___ ___ ___
| 1 | 2 | 3 | 4 | 7 | | 6 | 5 |
插入 6：
已排序 未排序
___ ___ ___ ___ ___ ___ ___
| 1 | 2 | 3 | 4 | 6 | 7 | | 5 |
插入 5：
已排序 未排序
___ ___ ___ ___ ___ ___ ___
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
经过 n 轮插入以后，数组就排好序了。
二、算法实现¶
public void insertSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
// 未排序区间数据元素
int x = arr[i];
int j = i;
// 插入到已排序区间合适的位置
for (; j > 0 && x < arr[j - 1]; j--) {
arr[j] = arr[j - 1];
}
arr[j] = x;
}
}
执行过程如下：
===== 初始数组 =====
[0, 3, 1, 6, 2, 5, 4]
=====第 1 轮插入=====
[0, 1, 3, 6, 2, 5, 4]
=====第 2 轮插入=====
[0, 1, 3, 6, 2, 5, 4]
=====第 3 轮插入=====
[0, 1, 2, 3, 6, 5, 4]
=====第 4 轮插入=====
[0, 1, 2, 3, 5, 6, 4]
=====第 5 轮插入=====
[0, 1, 2, 3, 4, 5, 6]
三、算法分析¶
3.1 时间复杂度¶
- 最好时间复杂度：O(n)
- 最坏时间复杂度：O(n^2)
- 平均时间复杂度：O(n^2)
3.2 空间复杂度¶
- 空间复杂度：O(1)
- 原地算法
3.3 稳定性¶
- 稳定排序算法
附录¶
/**
* 插入排序
* <p>
* 时间复杂度：最好 O(n) 最差 O(n^2) 平均 O(n^2)
* <p>
* 空间复杂度：O(1)
* <p>
* 稳定性：稳定
*
* @author weijiaduo
* @since 2022/7/21
*/
public class InsertSort implements Sort {
@Override
public void sort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
// 未排序区间数据元素
int x = arr[i];
int j = i;
// 插入到已排序区间合适的位置
for (; j > 0 && x < arr[j - 1]; j--) {
arr[j] = arr[j - 1];
}
arr[j] = x;
}
}
}