直接插入排序
前言：在博客写这些文章的目的用于记录所学，怕以后忘了，如果哪里写的不对欢迎指正，谢谢！！
学习目标：掌握直接插入排序算法的原理和思想
一、前提知识
排序算法概念、时间复杂度。可前往此网址 排序算法学习01_算法基础介绍阅读
二、直接插入排序介绍
直接插入排序是属于插入排序中的一种简单的排序，它通过抽象两个序列，一个为正在排序的序列称之为有序序列，一个为未排序序列。
每次从未排序序列中取值放入有序序列，来完成排序，就像抽取扑克牌一样
三、直接插入排序工作原理
构建一个有序序列，接着取一个未排序序列中第一个元素，然后依次从后往前扫描有序序列中的符合条件的值进行比较，最终找到指定位置插入，成为一个有序序列中的值。然后继续判断未排序序列中的值
四、直接插入排序设计思路
1.根据工作原理要构建一个有序序列
- 所说构建，并不是真的再创建一个序列去接收，而是找已排序好的序列范围，然后剩余序列就可以慢慢进去比较。那我们就要先给出一个有序序列，则选择数列的第一位当成一个有序序列
2.未排序序列中的元素，进入有序序列中的过程
我们知道首先要保存待进入元素，然后从后到前扫描，到达目标位置执行插入。但是你要知道我们此时只有一个数组，如何往有序列表a[0] 和 a[1]之中插入元素呢？
-
假设上面图片，正是我们要排序的数列，要让2插入1和3之间，怎么做？可以这样实现：
- 每次扫描元素，发现符合条件，则让该有序数列往后移。
- 比如本来有序数列【排序为递增】为： { 1，3，5 }，待插入元素为2，从后往前遍历有序序列，看到元素5时符合条件，那么让元素5往后移，此时元素5将覆盖元素2，也就是在数组中a[3] = a[2]。然后原本a[2]这个位置就可以决定是否插入，进行判断
在这里插入图片描述
五、直接插入排序算法代码实现
要求对以下这个数列进行递增排序：{3，2，5，1，7，9，8}
package com.migu.sortingAlgorithm;
import java.util.Arrays;
/**
* 直接插入排序
*/
public class DirectInsertionSort {
public static void main(String[] args) {
int a[] = {3,2,5,1,7,9,8};
// 数列第一位已为有序序列，则从下一位开始判断是否选择插入
for(int i = 1;i < a.length;i++){
int insertVal = a[i]; // 保存待插入的值【根据设计思路第一点】
int insertIndex = i-1; // 从有序序列最后一位开始判断，也就是待插入值的前一位索引，该索引往前肯定都是已排序好的【根据设计思路第一点】
// 由于要求递增，那么就待插入元素小于有序列表中的值时，有序列表值就执行后移动作。然后需要注意数组索引不能越界
while (insertIndex >=0 && insertVal < a[insertIndex]){
// 【根据设计思路第二点】
a[insertIndex+1] = a[insertIndex]; // 此举将覆盖待插入的值，但我们已经提前保存了
insertIndex--; // 从后往前遍历
}
// while循结束inertIndex是还会再--的，所以对其+1。然后保存待插入的值
a[insertIndex+1] = insertVal;
}
System.out.println(Arrays.toString(a)); // 调用工具类输出
}
}
六、时间复杂度分析
讨论一个算法的时间复杂度，一般都是看最坏的情况： 简单选择排序算法的时间复杂度为O(n^2)。更多特殊情况请参考其他书籍或博客
七、总结
直接插入排序算法，不像冒泡排序和简单选择排序，每完成一次排序都会在数列某个位置最终确定元素。
直接插入排序不需要重复走访所有元素，每进行一次排序只在有序序列中走访并对数组上元素进行移动。性能比冒泡排序好比简单选择排序差点
缺点就是比如要做递增时，待添加元素是在有序序列中最小的，那么就要在数组上移动大量数据，极耗时间。
