插入排序算法的实现和优化~

插入排序的基本思想：

在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序插入到已排好序的记录子集中，直到将所有待排记录全部插入为止

直接插入排序：

直接插入排序是一种最基本的插入排序方法，元素的插入和排序同时进行，其基本操作为，如下图所示：

在这里插入图片描述

文字描述(以升序为例)：

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