基本思路：
- 从第二个元素开始进行排序，第二个元素与前面的第一个元素进行比较，如果大就保持不动，如果小于第一个元素就往前移。
- 然后第三个元素与前面已经排序好的元素（前两个）从右到左（从大到小）依次进行比较，直到被比较的数小于或等于第三个元素，然后插入到这个元素的后面。
- 重复上面的过程，直到最后一个元素比较完成，一共进行了 n-1 趟。
编程步骤：
使用 for-while 嵌套循环，for 循环为外层循环，在外层循环设置两个变量，一个待排序元素索引 insertIndex, 一个待排序元素的值 insertValue。然后进入 while 内层循环，比较待排序元素的值是否大于前一个元素，大于就不用排序，小于就交换值并且索引往前移一位继续进行比较。最后在外层循环将待排序元素的值赋予应该插入的数组位置。
平均时间复杂度
图示展示：
import java.util.Arrays; public class InsertSort { public static void main(String[] args) { int[] arr = {5,4,3,2,1,-1,-5,-3}; System.out.println("未排序数组："+ Arrays.toString(arr)); insertSort(arr); System.out.println("未排序数组："+ Arrays.toString(arr)); } public static void insertSort(int[] arr){ for (int i=1;i<arr.length;i++){//插入排序从第二个元素开始进行，// 所以这里i（作为索引）设为1，循环次数为arr.length-1; int insertIndex = i;//待插入元素的索引位置，循环中进行位置的移动 int insertValue = arr[i];//待插入元素的值，循环中值不会变 while (insertIndex - 1 >= 0 && insertValue < arr[insertIndex-1]){//当要排序的元素比前一个元素大时，并且待插入的元素的索引位置大于0（不在第一位）时，进入循环 arr[insertIndex] = arr[insertIndex-1];//每次arr[i]<arr[i-1],就把arr[i-1]的值往后移，直到arr[i]>arr[i-1] insertIndex--; } arr[insertIndex] = insertValue; //insertValue 在比较过程中一直没变，最后一步将insertValue的值赋给insertIndex所指的元素 } } }
