算法入门-排序算法-插入排序-详解

一、核心思想

首先：把要排序的数组看作两部分：有序部分和无序部分
初始情况：有序数组只有一个元素即第一个元素
主要操作：将无序数组中的元素插入到有序数组中，并保证有序数组的有序性
需要将index=i的元素与index=i-1的元素进行比较，如果nums[i-1]>nums[i]则把nums[i]插入到有序数组的合适位置（index=1之前的元素即为有序数组）
什么是合适位置：nums[i+1]>nums[i]>nums[i-1]

二、过程分析

从i=1 开始遍历当前数组： 需要处理的情况是：
nums[i-1]>nums[i] -->> currentIndex=i; currentVal=nums[i];
满足nums[i-1]>nums[i]条件时：需要在i之前的元素组成的数组中找到currentVal的合适位置
即需要对i之前的元素进行遍历与currentVal比较（设定指针为j，则j的取值范围为：[0,i-1]），
如果nums[currentIndex]<nums[j]则交换这两个元素的位置，且需要对currentIndex做自减操作(因为当前要比较的元素的位置已经向前移动了一次)

三、代码

    public void test(){
        int[] orgNums=new int[]{1,5,3,9,6,4};
        for (int i=1;i<orgNums.length;i++){
            if (orgNums[i-1]>orgNums[i]){
                int currentIndex=i;
                int currentVal=orgNums[i];
                for (int j=currentIndex-1;j>=0;j--){
                    if (currentVal<orgNums[j]){
                        int temp=currentVal;
                        orgNums[currentIndex]=orgNums[j];
                        orgNums[j]=temp;
                        currentIndex=currentIndex-1;
                    }
                }
            }
        }

    }