排序算法 - 5.插入排序 插入排序的原理： 一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增 1 的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动 。 选择排序的基本思想是： 将未排序的元素一个一个地插入到有序的集合中，插入时把所有有序集合从后向前扫一遍，找到合适的位置插入。 public static void main(String[] args) { int[] arr = {1456, 22, 2378, 7867, 14, 87, 57, 9, 3}; //默认认为第一个元素是排序好的,所以从第二个元素开始 for (int i = 1; i < arr.length; i++) { //从当前 i 的这个元素的前一个位置开始，往最前面找 for (int j = i; j > 0; j--) { //如果找到比一个小的数，就交换一下 if (arr[j]<arr[j - 1]) { swap(arr, j, j - 1); } //发现前面的数比 i 大， 说明前面已经没有比它更小的了 无需再找，退出本次循环 else { break; } } } for (int i : arr) { System.out.println(i); } } private static void swap(int[] arr, int indexA, int indexB) { int temp = arr[indexA]; arr[indexA] = arr[indexB]; arr[indexB] = temp; } 平均时间复杂度：O(N^2) 最差时间复杂度：O(N^2) 空间复杂度：O(1) 排序方式：In-place 稳定性：稳定