插入排序（Insertion Sort）是一种简单直观的排序算法，它的工作原理是通过构造一个有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序在最好的情况下（输入数组已经是有序的），只需进行n-1次比较，时间复杂度为O(n)；但在最坏的情况下（输入数组是逆序的），需要进行大约n*(n-1)/2次比较和交换，时间复杂度为O(n²)。由于其对小规模数据集或部分有序数据集的高效性，插入排序常用于小数组排序或作为其他复杂排序算法（如快速排序）的辅助排序。此外，插入排序是稳定的排序算法，即相等的元素排序后相对位置不变。
以下为插入排序的基本步骤：
从第一个元素开始，该元素可以认为已经被排序。
取出下一个元素，在已经排序的元素序列中从后向前扫描。
如果该元素（已排序）大于新元素，将该元素移到下一位置。
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
将新元素插入到该位置后。
重复步骤2~5，直到所有元素均被扫描完成。
以下是Java实现插入排序的代码：
public class InsertionSort {
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
// 将arr[i]元素向左移动，直到找到合适的位置
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key; // 插入key到正确的位置
}
}
public static void main(String[] args) {
int[] array = {64, 34, 25, 12, 22, 11, 90};
insertionSort(array);
System.out.println(Arrays.toString(array));
}
}在这段代码中，通过一个for循环遍历数组中的每一个元素，然后使用while循环将当前元素与其左侧已排序的元素逐个比较并进行交换，最终将当前元素放到它在有序序列中的正确位置。
原文链接: https://www.yukx.com/arithmetic/article/details/2470.html 优科学习网插入排序算法
