插入排序和希尔排序--java

}

}

return arr;

}

}

结果：

beginTime:Mon Dec 03 14:07:15 CST 2018

endTime:Mon Dec 03 14:07:15 CST 2018

耗时（ms）21

12,33,34,43,45,45,46,54,57,64,80,90,123,343,534,623,35453,

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；

但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

算法步骤

1.选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

2.按增量序列个数 k，对序列进行 k 趟排序；

3.每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

代码：HillSort.java

import java.util.Date;

public class HillSort {

public static void main(String[] args) {

HillSort hillSort=new HillSort();

int[] array={33,45,12,45,46,43,90,34,57,80,123,343,54,35453,534,623,64};

Date beginTime=new Date();

System.out.println(“beginTime:”+beginTime);

hillSort.sort(array);

Date endTime=new Date();

System.out.println(“endTime:”+endTime);

System.out.println(“耗时（ms）”+(endTime.getTime()-beginTime.getTime()));

for(int i=0;i<array.length ;i++)

System.out.print(array[i]+“,”);

}

public int[] sort(int[] arr){

int gap = 1;

while (gap < arr.length) {

gap = gap * 3 + 1;

}

while (gap > 0) {

for (int i = gap; i < arr.length; i++) {

int tmp = arr[i];

int j = i - gap;

while (j >= 0 && arr[j] > tmp) {

arr[j + gap] = arr[j];

j -= gap;

}

arr[j + gap] = tmp;

}

gap = (int) Math.floor(gap / 3);

}

复习的面试资料

这些面试全部出自大厂面试真题和面试合集当中，小编已经为大家整理完毕（PDF版）

• 第一部分：Java基础-中级-高级

• 第二部分：开源框架（SSM：Spring+SpringMVC+MyBatis）

• 第三部分：性能调优（JVM+MySQL+Tomcat）

• 第四部分：分布式（限流：ZK+Nginx；缓存：Redis+MongoDB+Memcached；通讯：MQ+kafka）

• 第五部分：微服务（SpringBoot+SpringCloud+Dubbo）

• 第六部分：其他：并发编程+设计模式+数据结构与算法+网络

进阶学习笔记pdf

• Java架构进阶之架构筑基篇（Java基础+并发编程+JVM+MySQL+Tomcat+网络+数据结构与算法）

• Java架构进阶之开源框架篇（设计模式+Spring+SpringMVC+MyBatis）

• Java架构进阶之分布式架构篇 （限流（ZK/Nginx）+缓存（Redis/MongoDB/Memcached）+通讯（MQ/kafka））

• Java架构进阶之微服务架构篇（RPC+SpringBoot+SpringCloud+Dubbo+K8s）

[外链图片转存中…(img-Z3bwdT0X-1714200874861)]

• Java架构进阶之微服务架构篇（RPC+SpringBoot+SpringCloud+Dubbo+K8s）

[外链图片转存中…(img-0xFMsmH0-1714200874862)]

[外链图片转存中…(img-DgHxfH4s-1714200874862)]

本文已被CODING开源项目：【一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频+实战项目源码】收录