16 -- 排序算法之插入排序

算法介绍：

插入排序属于内部排序法，时对于待排序的元素以插入的方式找到改元素的适当位置，以达到排序的目的。【类似于生活中的斗地主游戏，每抓起一张牌按照便把改张牌按照指定的顺序插入到适当的位置】

插入排序的基本思想：

把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无需表中取出第一个元素，把它的排序码依次与有序元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

思路图：

 动态效果图演示：https://www.bilibili.com/video/BV1Ck4y1B7N4?share_source=copy_web&vd_source=7db086eb00bd8fed934c0bb84de86a58

 1 import java.util.Arrays;
 2 //插入排序
 3 public class InsertSort {
 4 
 5     public static void main(String[] args) {
 6         int[] arr = {10,34,119,2};
 7         insertSort(arr);
 8         System.out.println(Arrays.toString(arr));
 9     }
10     
11     public static void insertSort(int[] arr) {
12         for (int i = 1; i < arr.length; i++) {
13             insert(arr, i);
14         }
15     }
16     
17     /**
18      * @param arr 数组
19      * @param n 待插入的数的索引
20      */
21     public static void insert(int[] arr,int n) {
22         int insertValue = arr[n];
23         while(arr[n-1] > insertValue) {
24             arr[n] = arr[n-1];
25             n--;
26             if (n == 0) {
27                 break;
28             }
29         }
30         arr[n] = insertValue; 
31     }
32     
33 }