目录
前言
在 Java 中， 冒泡排序（Bubble Sort） 和 选择排序（Selection Sort） 之后，下一个性能更好的排序算法通常是 插入排序（Insertion Sort）。
虽然它们的时间复杂度都是 O(n²)，但在实际应用中，插入排序通常比选择排序和冒泡排序更快，尤其是在处理部分有序数据时表现更优。
总结：Java 排序算法进阶路线
O(n²) 算法（适合学习原理）
冒泡排序（最慢）→ 选择排序 → 插入排序（推荐先学）
O(n log n) 算法（实际应用）
归并排序（稳定）→ 快速排序（最快，但不稳定）→ 堆排序（空间省）
Java 内置排序
Arrays.sort()：对基本类型用 快速排序，对象类型用 归并排序（保证稳定性）。
1、插入排序
Insertion Sort：插入排序是一种简单直观的排序算法，适合小规模数据或部分有序数据。
1、核心思想
将数组分为 已排序 和 未排序 两部分，逐个将未排序部分的元素插入到已排序部分的正确位置。
2、适合场景
小规模数据或基本有序的数据（如日志按时间插入）。
3、时间复杂度：
最坏情况下为O(N*N)，此时待排序列为逆序，或者说接近逆序。
最好情况下为O(N)，此时待排序列为升序，或者说接近升序。
4、空间复杂度：O(1)。
2、流程介绍
如下图所示：
步骤：
1.从第一个元素开始，该元素可以认为已经被排序.
2.取下一个元素tem，从已排序的元素序列从后往前扫描.
3.如果该元素大于tem，则将该元素移到下一位.
4.重复步骤3，直到找到已排序元素中小于等于tem的元素.
5.tem插入到该元素的后面，如果已排序所有元素都大于tem，则将tem插入到下标为0的位置.
6.重复步骤2~5.
3、java实现
代码示例如下：
public class InsertionSort {
/**
* 插入排序（升序）
* @param arr 待排序数组
*/
public static void insertionSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return; // 边界条件：数组为空或长度≤1时无需排序
}
// 从第二个元素开始（下标1），默认第一个元素已排序
for (int i = 1; i < arr.length; i++) {
int current = arr[i]; // 当前待插入的元素
int j = i - 1; // 已排序部分的最后一个元素下标
// 从后往前遍历已排序部分，寻找插入位置
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j]; // 比 current 大的元素向后移动
j--;
}
// 插入 current 到正确位置
arr[j + 1] = current;
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6};
System.out.println("排序前: " + Arrays.toString(arr));
insertionSort(arr);
System.out.println("排序后: " + Arrays.toString(arr));
}
}输出：
排序前: [12, 11, 13, 5, 6]
排序后: [5, 6, 11, 12, 13]关键步骤解析
外层循环：
从
i = 1开始（默认arr[0]是已排序部分）。每次迭代处理一个未排序元素
current = arr[i]。
内层循环：
从
j = i - 1开始，反向遍历已排序部分。如果
arr[j] > current，则将arr[j]向后移动一位。直到找到
arr[j] ≤ current的位置，此时j + 1就是current的插入位置。
插入操作：
将
current放入arr[j + 1]。
4、性能介绍
✅ 为什么插入排序比选择排序快？
比较次数更少：选择排序每一轮都要遍历剩余全部元素找最小值，而插入排序在数据基本有序时只需少量比较。
提前终止：如果数据已经有序，插入排序内层循环会立即终止（类似冒泡优化版）。
数据局部性：插入排序是顺序访问数组，对 CPU 缓存更友好。
总结
小数组排序：
Java 的
Arrays.sort()在子数组长度 ≤ 47 时，会切换到插入排序。
部分有序数据：
如日志按时间插入、游戏排行榜实时更新。
混合排序算法：
快速排序的递归基改用插入排序（如
QuickSort + InsertionSort）。
参考文章：
https://blog.csdn.net/weixin_50886514/article/details/119045154?ops_request_misc=%257B%2522request%255Fid%2522%253A%25220faf03d22b2d125d5f49a4649ad59c85%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=0faf03d22b2d125d5f49a4649ad59c85&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-119045154-null-null.142^v102^control&utm_term=%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F&spm=1018.2226.3001.4187