一、核心思想插入排序把数组分成两部分左侧已排序区间、右侧未排序区间默认第 0 个元素天然有序已排序区间[0]依次取出未排序区间第一个元素记为待插入元素向前遍历有序区间比待插入元素大的元素统一向后挪动一位找到合适空位将待插入元素放入循环直到所有元素完成插入。算法特性面试重点时间复杂度 最坏 / 平均 \(O(n^2)\)最好情况 (数组已有序) \(O(n)\)稳定排序适合小规模数据、接近有序的数据二、完整代码升序java运行public class InsertSort { public static void main(String[] args) { int[] arr {5, 2, 9, 3, 7, 6, 1}; System.out.println(排序前); printArr(arr); insertSort(arr); System.out.println(排序后); printArr(arr); } /** * 插入排序 升序 */ public static void insertSort(int[] arr) { int len arr.length; // i从1开始arr[0]默认有序从第二个元素开始处理 for (int i 1; i len; i) { // 当前要插入的元素 int temp arr[i]; // j指向有序区间末尾 int j i - 1; // 向前遍历有序区间大于temp的元素后移 while (j 0 arr[j] temp) { arr[j 1] arr[j]; j--; } // j1 就是temp插入的位置 arr[j 1] temp; } } // 打印数组 public static void printArr(int[] arr) { for (int num : arr) { System.out.print(num ); } System.out.println(); } }三、简单推演示例数组[5,2,9,3]i1temp2 j0arr[0]52 → arr[1]5j-1 arr[0]2 →[2,5,9,3]i2temp9 arr [1]5 9不用移动直接原位放置i3temp3 j2:93 → arr [3]9j1 j1:53 → arr [2]5j0 j0:23停止arr [1]3 最终[2,3,5,9]四、冒泡 / 选择 / 插入 快速区分冒泡排序相邻比较边比较边交换大数逐步往后浮选择排序一轮找到最值下标一轮最多交换 1 次插入排序逐个拿元素向前找位置、元素后移插入空位
一、核心思想插入排序把数组分成两部分左侧已排序区间、右侧未排序区间默认第 0 个元素天然有序已排序区间[0]依次取出未排序区间第一个元素记为待插入元素向前遍历有序区间比待插入元素大的元素统一向后挪动一位找到合适空位将待插入元素放入循环直到所有元素完成插入。算法特性面试重点时间复杂度 最坏 / 平均 \(O(n^2)\)最好情况 (数组已有序) \(O(n)\)稳定排序适合小规模数据、接近有序的数据二、完整代码升序java运行public class InsertSort { public static void main(String[] args) { int[] arr {5, 2, 9, 3, 7, 6, 1}; System.out.println(排序前); printArr(arr); insertSort(arr); System.out.println(排序后); printArr(arr); } /** * 插入排序 升序 */ public static void insertSort(int[] arr) { int len arr.length; // i从1开始arr[0]默认有序从第二个元素开始处理 for (int i 1; i len; i) { // 当前要插入的元素 int temp arr[i]; // j指向有序区间末尾 int j i - 1; // 向前遍历有序区间大于temp的元素后移 while (j 0 arr[j] temp) { arr[j 1] arr[j]; j--; } // j1 就是temp插入的位置 arr[j 1] temp; } } // 打印数组 public static void printArr(int[] arr) { for (int num : arr) { System.out.print(num ); } System.out.println(); } }三、简单推演示例数组[5,2,9,3]i1temp2 j0arr[0]52 → arr[1]5j-1 arr[0]2 →[2,5,9,3]i2temp9 arr [1]5 9不用移动直接原位放置i3temp3 j2:93 → arr [3]9j1 j1:53 → arr [2]5j0 j0:23停止arr [1]3 最终[2,3,5,9]四、冒泡 / 选择 / 插入 快速区分冒泡排序相邻比较边比较边交换大数逐步往后浮选择排序一轮找到最值下标一轮最多交换 1 次插入排序逐个拿元素向前找位置、元素后移插入空位
