Insertion Sort 插入排序
插入排序（Insertion Sort）的思路是将未排序的元素逐个插入到已排序的部分中，构建有序序列。初始时，将第一个元素视为已排序部分，然后依次将后续的元素插入到已排序部分的正确位置。
具体的插入排序算法步骤如下：
- 假设待排序的数组为arr，初始时将arr[0]视为已排序部分，将其作为初始的有序序列。
- 从第二个元素开始（索引为1），将其与已排序部分的元素逐个比较。
- 将当前元素与已排序部分的元素从右到左依次比较，找到合适的插入位置。
- 插入当前元素到已排序部分的正确位置，同时将插入位置右侧的元素依次后移。
- 重复步骤2-4，直到所有元素都被插入到已排序部分，完成排序。
public class InsertionSort { public static void insertionSort(int[] array) { for (int i = 1; i < array.length; i++) { int key = array[i]; int j = i - 1; // 将元素插入到已排序部分的正确位置 while (j >= 0 && array[j] > key) { array[j + 1] = array[j]; j--; } array[j + 1] = key; } } public static void main(String[] args) { int[] array = {5, 2, 8, 12, 1, 6}; insertionSort(array); System.out.println("排序结果："); for (int num : array) { System.out.print(num + " "); } } }
以上代码中，insertionSort方法实现了插入排序算法。通过一个外层循环和内层的while循环，将未排序的元素逐个插入到已排序的部分中。main方法中使用一个示例数组进行排序，并输出排序结果。
插入排序的时间复杂度为O(n^2)，其中n是待排序列表的元素个数。
空间复杂度为O(1)，因为只需要常量级的额外空间来存储临时变量。
需要注意的是，插入排序是一种稳定的排序算法，即相等元素的相对顺序在排序后保持不变。
