以下是插入排序的详细解析，包含基础实现、常见变体的完整代码示例，以及各变体的对比表格：
一、插入排序基础实现
原理
将元素逐个插入到已排序序列的符合位置，逐步构建有序序列。
代码示例
- public class InsertionSort {
- void sort(int[] arr) {
- int n = arr.length;
- for (int i = 1; i < n; i++) {
- int key = arr[i]; // 待插入的元素
- int j = i - 1;
- // 将比 key 大的元素后移
- while (j >= 0 && arr[j] > key) {
- arr[j + 1] = arr[j];
- j--;
- }
- arr[j + 1] = key; // 插入到正确位置
- }
- }
- }
- 时间复杂度：
- 最坏/平均：O(n²)（逆序或随机数据）。
- 最好（已有序）：O(n)。
- 空间复杂度：O(1)。
- 稳固性：稳固（雷同值的元素相对顺序稳固）。
二、常见变体及代码示例
1. 优化版（减少移动次数）
改进点：通过减少元素移动的次数，优化内层循环。
实用场景：数据靠近有序时效率更高。
- public class OptimizedInsertionSort {
- void sort(int[] arr) {
- int n = arr.length;
- for (int i = 1; i < n; i++) {
- int key = arr[i];
- int j = i - 1;
- // 找到插入位置后一次性移动元素
- while (j >= 0 && arr[j] > key) {
- j--;
- }
- // 将 j+1 到 i 的元素后移一位
- for (int k = i; k > j + 1; k--) {
- arr[k] = arr[k - 1];
- }
- arr[j + 1] = key;
- }
- }
- }
改进点：用二分查找确定插入位置，减少比力次数。
实用场景：数据规模较大时，减少比力时间。
- public class BinaryInsertionSort {
- void sort(int[] arr) {
- int n = arr.length;
- for (int i = 1; i < n; i++) {
- int key = arr[i];
- int left = 0, right = i - 1;
- // 二分查找插入位置
- while (left <= right) {
- int mid = (left + right) / 2;
- if (arr[mid] > key) {
- right = mid - 1;
- } else {
- left = mid + 1;
- }
- }
- // 移动元素并插入
- for (int j = i - 1; j >= left; j--) {
- arr[j + 1] = arr[j];
- }
- arr[left] = key;
- }
- }
- }
改进点：用递归替代循环，代码结构更清晰。
实用场景：讲授或代码风格偏好递归。
- public class RecursiveInsertionSort {
- void sort(int[] arr, int n) {
- if (n <= 1) return;
- sort(arr, n - 1); // 先排序前 n-1 个元素
- int key = arr[n - 1];
- int j = n - 2;
- // 将比 key 大的元素后移
- while (j >= 0 && arr[j] > key) {
- arr[j + 1] = arr[j];
- j--;
- }
- arr[j + 1] = key;
- }
- }
三、变体对比表格
变体名称时间复杂度空间复杂度稳固性主要特点实用场景基础插入排序O(n²)（平均/最坏），
O(n)（最好）O(1)稳固简单易实现，适合小规模或部门有序数据小数据或靠近有序的场景优化版（减少移动次数）O(n²)（平均/最坏），
O(n)（最好）O(1)稳固减少内层循环的移动次数数据靠近有序时效率提拔二分插入排序O(n²)（平均/最坏），
O(n log n)（比力次数）O(1)稳固用二分查找减少比力次数数据规模较大时减少比力时间递归实现O(n²)（全部情况）O(n)稳固递归替代循环，代码结构清晰讲授或代码风格偏好递归的场景
四、关键选择原则
- 基础场景：优先利用基础实现，因其简单且实用于小规模数据。
- 优化需求：
- 靠近有序数据：优化版（减少移动次数）可提拔效率。
- 大规模数据：二分插入排序通过减少比力次数优化性能。
- 代码风格：递归实现适合讲授或偏好函数式编程的场景，但需注意栈空间开销。
- 稳固性需求：全部变体均稳固，实用于需要保持元素相对顺序的场景（如排序带键值的记录）。
- 极端场景：已排序数据时，基础实现的时间复杂度降至 O(n)，是插入排序的优势场景。
通过选择符合的变体，可在特定场景下优化性能或代码可读性，同时保持算法的稳固性。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
