一、直接插入排序

插入排序（英语：Insertion sort）是一种简单直观的排序算法。它的工作原理为将待排列元素划分为「已排序」和「未排序」两部分，每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置。

一个与插入排序相同的操作是打扑克牌时，从牌桌上抓一张牌，按牌面大小插到手牌后，再抓下一张

稳定性：直接插入排序是一种稳定的排序算法。

时间复杂度：插入排序的最优时间复杂度为O(n)，在数列几乎有序时效率很高。

　　　　　　插入排序的最坏时间复杂度和平均时间复杂度都为O(n²)。

二、思想及代码实现

package algo;

import java.util.Arrays;

/**
 * 直接插入排序是插入排序的一种，也是最为简单的一种插入排序。
 * 大致思路是：
 * 初始将数组中的第一个元素nums[0]看成一个有序数组，随后不断的将无序数组即下标为[1, nums.length - 1]的元素插入到有序数组中。
 * 
 * 举例说明：假设现有一待排序的数组{3， 6， 5， 8， 0， 2， 1}，
 * 那么第一步就是将数组中的第一个元素看成一个有序数组即{3}，随后遍历无序数组的元素往有序数组中插入。
 * 对于第二个元素6来讲，它是大于3的，则不需要操作，此时子数组就变成了{3，6}；
 * 对于第三个元素5来讲，它是小于它前面的元素6的，那么下面要做的就是在子数组{3，6}的合适位置将5插进去，
 * 这里记待插入元素的值为temp = 5（之所以需要进行记录，是因为后续随着有序数组的比较和后移，会将数组中的5覆盖掉），
 * 之后对有序数组进行倒序的遍历并分别和待插入元素temp比较：
 * 若有序数组中的某个元素大于temp，则直接将该元素后移一位，覆盖掉其后面的一个元素，比如这里就是 6 把 5 给覆盖了，这里是一个不断循环的操作，
 * 直至达到j < 0 || temp > nums[j]时停止，并将temp插入到nums[j + 1]的位置。
 * 这里有两种情况，第一种情况是当遇到j < 0时表示有序数组中不存在比5小的，那么5就会作为有序数组中的第一个元素
 * 第二种情况则是，temp > nums[j]，这里表达的意思是随着对有序数组的遍历，找到了一个nums[j] < temp的元素，那么随后将temp插入到nums[j + 1]的位置即可。
 * 
 */

public class insertSortSolution {
    public static void insertSort(int[] nums){
        for(int i = 1; i < nums.length; i++){ // 初始将第一个元素，也就是索引为0的元素看成一个有序数组
            if(nums[i] < nums[i - 1]){ // 若待插入的元素比有序数组中的元素小的话，表明该元素待插入到有序数组中
                int temp = nums[i]; // 将该值记录（因为后续要进行覆盖操作），并准备插入到前面的有序数组中
                int j = i - 1;
                while(j >= 0 && temp < nums[j]){ // 从有序数组的最后一个元素开始逐个和待插入元素比较
                    nums[j+1] = nums[j]; // 覆盖操作
                    j--;
                }
                nums[j + 1] = temp; // 将待插入元素放入到合适的位置
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{3, 2, 1, 0, 5, 6, 7, 4};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}