插入排序 (Insertion Sort)
插入排序是一种简单直观的排序算法，它的工作方式类似于人们按数字或字母顺序整理扑克牌的方法。
算法原理
插入排序的基本思想是：将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行数据的移动。
时间复杂度
O(n²)
空间复杂度
O(1)
稳定性
稳定
算法步骤
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
代码实现
public class InsertionSort {
public static void insertionSort(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--;
}
// 插入key到正确位置
arr[j + 1] = key;
}
}
// 测试方法
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
System.out.println("排序前:");
printArray(arr);
insertionSort(arr);
System.out.println("排序后:");
printArray(arr);
}
static void printArray(int[] arr) {
for (int value : arr) {
System.out.print(value + " ");
}
System.out.println();
}
}应用场景
- 小规模数据排序：当数据量较小时，性能表现良好
- 基本有序的数据：对于已经基本有序的数据，效率很高
- 在线排序：可以在接收数据的同时进行排序
- 作为其他高级排序算法的子过程：如快速排序中的小数组排序
优缺点
优点
- 实现简单，容易理解和编程
- 稳定排序算法
- 原地排序算法，空间复杂度低
- 对于小规模数据或基本有序的数据效率很高
- 是自适应的，对于不同的输入有不同的时间复杂度
缺点
- 对于大规模乱序数组，时间复杂度较高
- 每次只能将数据移动一位，效率较低