当前位置：首页 > ds >正文

【算法基础】插入排序算法 - JAVA

ds 2025/5/5 8:02:29

一、算法基础

1.1 什么是插入排序

插入排序是一种简单直观的排序算法，它的工作原理类似于我们打牌时整理手牌的过程。插入排序的核心思想是将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的适当位置。

1.2 插入排序的基本思想

将第一个元素视为已排序部分
取出下一个元素，在已排序部分找到合适的插入位置
将已排序部分中大于该元素的所有元素后移一位
将该元素插入到正确的位置
重复步骤2~4，直到所有元素都插入到正确的位置

1.3 时间复杂度

最佳情况：O(n)，当数组已经排好序时
最坏情况：O(n²)，当数组逆序排列时
平均情况：O(n²)
空间复杂度：O(1)，原地排序算法

二、插入排序的实现

2.1 标准实现

public class InsertionSort {public static 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--;}// 将key插入到正确位置arr[j + 1] = key;}}
}

2.2 优化实现（针对部分有序数组）

public class OptimizedInsertionSort {public static void sort(int[] arr) {int n = arr.length;// 找到第一个逆序位置int startIndex = 1;for (int i = 0; i < n - 1; i++) {if (arr[i] > arr[i + 1]) {startIndex = i + 1;break;}}// 从startIndex开始进行插入排序for (int i = startIndex; i < n; i++) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}}
}

2.3 二分查找优化

在插入过程中，可以使用二分查找来加速查找插入位置：

public class BinaryInsertionSort {public static void sort(int[] arr) {int n = arr.length;for (int i = 1; i < n; i++) {int key = arr[i];// 使用二分查找找到插入位置int insertPos = binarySearch(arr, 0, i - 1, key);// 将元素后移if (insertPos < i) {System.arraycopy(arr, insertPos, arr, insertPos + 1, i - insertPos);arr[insertPos] = key;}}}// 二分查找最小的不小于key的元素位置private static int binarySearch(int[] arr, int low, int high, int key) {while (low <= high) {int mid = low + (high - low) / 2;if (arr[mid] > key) {high = mid - 1;} else {low = mid + 1;}}return low;}
}

三、插入排序的特点分析

3.1 优点

实现简单：算法逻辑直观，容易理解和实现
稳定排序：相同元素的相对位置在排序后保持不变
原地排序：不需要额外空间
对小规模数据高效：当数据量小时，常数因子小，效率高
对近乎有序的数据非常高效：接近O(n)时间复杂度
在线算法：可以一边读取数据一边排序

3.2 缺点

时间复杂度高：对于大规模数据，O(n²)的时间复杂度较高
不适合逆序数组：在逆序数组上性能最差
不适合频繁交换元素的场景：在交换代价高的情况下可能效率低下

四、实际应用示例

4.1 完整示例程序

public class InsertionSortDemo {public static void main(String[] args) {// 示例数组int[] arr = {12, 11, 13, 5, 6, 7};System.out.println("原始数组:");printArray(arr);// 执行插入排序insertionSort(arr);System.out.println("排序后数组:");printArray(arr);}// 插入排序算法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 printArray(int[] arr) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}
}