目录

插入排序

插入排序的核心图解

希尔排序

希尔排序详细图解

插入排序

插入排序的交换精髓在于 每次随着i的扩大,i走过的路径都是有序的,这和冒泡的思想有异曲同工之处,冒泡是i走一次,数组的最后变成有序的,而插入排序是

插入排序是 i 在前面  j在后面

插入排序的核心图解:

我现在有如下数组:
int []arr ={4,6,9,1,11,5,14,6};

我们依旧和冒泡排序一样需要两个指针 这次就是 i 和  j

重点在于:每次随着i的扩大,i走过的路径都是有序的

我们发现0到2,也就是前三个都是有序的! 

于是等到i的值为3的时候

注意观测j和i的位置!!!

1是小于9的,所以触发交换

此时发现1还是比前一个 6小 ,所以必须贯彻 每次随着i的扩大,i走过的路径都是有序的

1是小于6的,所以触发交换

接着 是1和4的交换

 自此i走过的路程都是有序的了

此后就是不断重复这个过程,直到i走到数组的末尾!

整个数组也有序了!

Java代码

//插入排序static  void insertSort(int []arr){for (int i = 1; i < arr.length; i++) {for (int j = i-1; j >=0; j--) {if (arr[j]>arr[j+1]){//判断条件swap(arr,j,j+1);}else {break;}}}}//交换函数static void swap(int []arr,int x,int y){int tmp=arr[x];arr[x]=arr[y];arr[y] = tmp;}

不难看出这个的时间复杂度是O(N^2)

(什么你还不会看时空间复杂度?建议你去b站恶补一下...)

希尔排序

不是这个希尔!

希尔排序，也称为缩小增量排序，是一种基于插入排序的排序算法。它通过比较距离较远的元素，将较小的元素交换到前面，从而逐步减小数组的无序程度，最终实现数组的排序。

她的精髓就在于---分组! 在插入排序的基础上进行分组

一般选择是 将数组分成arr.length/2 然后再把分组范围扩大

比如

第一次这个数组 选择分4组 ,下一次就分成2组

分组后进行选择排序,在数据量小的情况下和插入排序差不多,但是数据量的时候比插入排序快很多

为什么快很多?我也不知道,数学家算出来的,就是快很多

希尔排序的时间复杂度和增量序列的选择有关系，一般情况下希尔排序的时间复杂度为O(n^2) ~ O(n^1.5)。空间复杂度为O(1)，是一种原地排序算法。

希尔排序详细图解:

第一次分组,同一个组别的进行选择排序

第二次分组

分组后,排序后的结果

 箭头指向的是交换了的位置

我们发现每次组员都会扩大2倍,这个数组到第3次就变成了进行一次选择排序了

所有的希尔排序,到最后都会进行一次完整的选择排序,但是此时数组已经趋近于有序了

 再来回顾一下

1. 选择一个增量序列，增量序列是一个数组，一般是按照一定的规则(这里是2)生成的；
2. 对于每个增量，将数组分为若干个子序列，子序列中的元素相隔增量个位置；
3. 对每个子序列进行插入排序，即将每个子序列看成一个独立的数组进行插入排序；
4. 增量为1时，进行一次插入排序，排序结束。

Java代码

  //交换函数static void swap(int []arr,int x,int y){int tmp=arr[x];arr[x]=arr[y];arr[y] = tmp;}//希尔排序static  void shellSort(int []arr){for (int k= arr.length/2;k > 0; k/=2){//要不要取等号?不用for (int i = k; i < arr.length ; i++) {//i和j的范围取值和插入排序一致for (int j = i-k; j >=0 ; j-=k) {if (arr[j]>arr[j+k]){swap(arr,j,j+k);}else {break;}}}}

哈，谢谢各位同志的阅读，然后呢如果觉得本文对您有所帮助的话，还给个免费的赞捏

Thanks♪(･ω･)ﾉ