插入排序的基本思想：
在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序插入到已排好序的记录子集中，直到将所有待排记录全部插入为止
直接插入排序：
直接插入排序是一种最基本的插入排序方法，元素的插入和排序同时进行，其基本操作为，如下图所示：
文字描述(以升序为例)：
1：将数组分为两个区域，排序区域和未排序区域，每一轮从未排序区域中取出第一个元素，插入到排序区域(需保证顺序)
2：重复以上步骤，直到整个数组有序
package bin_find; import java.util.Arrays; public class Insert_sort { public static void main(String[] args) { int arr[]={3,1,29,4,8,10,71,22}; sort(arr); } public static void sort(int arr[]){ //起初将数组的第一个元素视为有序区域，剩下元素即为无序区域，因此无序区域应为下标为1的元素 for(int i=1;i<arr.length;i++){ //暂存区域的元素始终为无序区域的第一个元素 int t=arr[i]; //j始终为有序区域的最后一个元素下标 int j=i-1; //该循环完成的是比较＋移动的操作，循环次数为比较次数，也就是有序数组的长度 while(j>=0){ //当暂存区域元素小于有序区域的最后一个元素时 if(t<arr[j]){ //将有序区域的元素向后移动一位 arr[j+1]=arr[j]; } //否则本轮排序结束 else{ break; } j--;//表示将暂存区域的元素与有序区域的元素一一进行比较，直到比较完有序区域的第一个元素 } arr[j+1]=t;//将元素插入对应的位置 System.out.println("第"+i+"趟插入排序的结果为："+Arrays.toString(arr)); } } }
输出如下：
第1趟插入排序的结果为：[1, 3, 29, 4, 8, 10, 71, 22] 第2趟插入排序的结果为：[1, 3, 29, 4, 8, 10, 71, 22] 第3趟插入排序的结果为：[1, 3, 4, 29, 8, 10, 71, 22] 第4趟插入排序的结果为：[1, 3, 4, 8, 29, 10, 71, 22] 第5趟插入排序的结果为：[1, 3, 4, 8, 10, 29, 71, 22] 第6趟插入排序的结果为：[1, 3, 4, 8, 10, 29, 71, 22] 第7趟插入排序的结果为：[1, 3, 4, 8, 10, 22, 29, 71]
优化方式：
1.待插入元素进行比较时，遇到比自己小的元素，就代表找到了插入位置，直接循环退出，无需进行后续比较
2.插入时可以直接移动元素，而不是交换元素
与选择排序比较:
1：二者平均时间复杂度都是 0(n^2) 2：大部分情况下，插入都略优于选择 3：有序集合插入的时间复杂度为 0(n) 4：插入属于稳定排序算法，而选择属于不稳定排序
上述的选择排序并不是最优的，当某些元素从起始位置移动到最终位置需要移动的次数过多时，这会很麻烦，如下所示：
假设我们需要将下述的无序数组通过插入排序使之成为有序数组，那么元素9会移动7次！
对于这种情况，我们可以使用希尔排序！
希尔排序：[掌握思路]
步骤：
以上述实例为例进行：
第一步：选择间距为4的元素进行插入排序
排序后的结果为：
第2步：选择间距为2的元素进行插入排序
排序后的结果为：
第3步：选择间距为1的元素进行插入排序，也就是普通的插入排序，排序结果如下：
使用希尔排序，我们通过上述步骤，可以看出元素9只移动了3次
对于间隙的选择是多种多样的，不同的队列选择它的时间复杂度也是不同的，这里我们主要学习它的思路
练习题：
one：
答案为：9,18,19,23,23，15
two:
答案为：9,15,18,19,23,23
