直接插入排序（Straight Insertion Sort），通常简称为插入排序，是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。本文将详细介绍插入排序的原理、Java 实现、优化方法以及其性能分析。
一、插入排序的基本原理
插入排序的基本思想是：
- 将第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
- 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。
- 如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。
二、java实现
基本实现：
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 = j - 1;}arr[j + 1] = key;}}public static void main(String[] args) {int[] arr = {12, 11, 13, 5, 6};System.out.println("排序前的数组：");printArray(arr);insertionSort(arr);System.out.println("排序后的数组：");printArray(arr);}public static void printArray(int[] arr) {for (int i : arr) {System.out.print(i + " ");}System.out.println();}
}
三、优化方法
1、二分查找优化
使用二分查找来找到插入位置，可以减少比较次数。
public static void binaryInsertionSort(int[] arr) {for (int i = 1; i < arr.length; i++) {int key = arr[i];int left = 0;int right = i - 1;while (left <= right) {int mid = left + (right - left) / 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;}
}
2、希尔排序
希尔排序是插入排序的一种更高效的改进版本。它先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序。
public static void shellSort(int[] arr) {int n = arr.length;// 初始间隔for (int gap = n / 2; gap > 0; gap /= 2) {// 对每个子序列进行插入排序for (int i = gap; i < n; i++) {int temp = arr[i];int j;for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;}}
}
四、性能分析
1、时间复杂度
- 最坏情况：O(n^2) - 当输入数组是反向排序的时候
- 最好情况：O(n) - 当输入数组已经排好序的时候
- 平均情况：O(n^2)
2、空间复杂度
插入排序是原地排序算法，只需要常数级的额外空间，因此空间复杂度为 O(1)。
3、稳定性
插入排序是稳定的排序算法。在排序过程中，相等的元素不会改变其相对顺序。
五、适用场景
插入排序适用于以下场景：
- 小规模数据：当数据量较小时，插入排序可能比更复杂的排序算法更快。
- 部分有序的数组：对于已经部分排序的数组，插入排序可以很快完成排序。
- 在线算法：可以在接收到新元素时直接插入到已排序的序列中。
六、插入排序优缺点
优点：
- 实现简单，容易理解
- 对于小规模数据或部分有序的数据效率较高
- 是稳定排序
- 原地排序，不需要额外的存储空间
- 适合作为在线算法
缺点：
- 对于大规模乱序数组，时间复杂度较高
- 元素移动次数较多
七、总结
插入排序是一种简单直观且稳定的排序算法。它在处理小规模数据或部分有序的数据时表现良好，而且作为在线算法具有独特的优势。虽然它的平均时间复杂度为 O(n^2)，不适合大规模数据排序，但在某些特定场景下仍然很有用。
插入排序的思想也被应用在一些更高效的排序算法中，如希尔排序。理解插入排序的工作原理对于深入学习更复杂的排序算法很有帮助。在实际应用中，需要根据数据的特性和规模来选择合适的排序算法，插入排序在处理小规模或近乎有序的数据时仍然是一个不错的选择。
参考链接：https://www.cnblogs.com/kenwan/p/18351406
