1 插入排序简介
插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动
2 插入排序思想及图解
插入排序的基本思想如下：
把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为一个新的有序表。
以序列：{55, 85, 21, 12, 5} 为例， 图解如下：
粉红色部分为每轮认定的有序部分，其余颜色为认定的无序部分。绿色标识为每轮遍历的无序序列的位置，将该位置的元素逐一与有序部分进行比较，找到合适的位置进行顺序表的插入操作。
3 插入排序代码实现
import java.util.Arrays; /** * @author 兴趣使然黄小黄 * @version 1.0 * 插入排序 */ public class InsertSort { public static void main(String[] args) { int[] array = {55, 85, 21, 12, 5}; System.out.println("排序前: " + Arrays.toString(array)); insertSort(array); System.out.println("排序后: " + Arrays.toString(array)); } //插入排序 public static void insertSort(int[] arr){ //边界条件 if (arr.length < 1){ return; } for (int i = 1; i < arr.length; i++) { //定义待插入的位置和待插入的数 int insertIndex = i-1; //arr[i]前面的位置,便于插入 int insertVal = arr[i]; //先将待插入的值保存 //给insertVal找到待插入的位置 //1.insertIndex > 0防止越界 //2.insertVal < arr[insertIndex] 说明还未找到待插入的位置 while (insertIndex >= 0 && insertVal < arr[insertIndex]){ arr[insertIndex+1] = arr[insertIndex]; insertIndex--; } if (insertIndex != i){ arr[insertIndex+1] = insertVal; //插入 } System.out.println("第" + i + "轮: " + Arrays.toString(arr)); } } }
结果如下
