前言
之前我们学习过基础排序，包括冒泡排序，选择排序还有插入排序，并且对他们在最坏情况下的时间复杂度做了分
析，发现都是O(N^2)，而平方阶通过我们之前学习算法分析我们知道，随着输入规模的增大，时间成本将急剧上
升，所以这些基本排序方法不能处理更大规模的问题，接下来我们学习一些高级的排序算法，争取降低算法的时间
复杂度最高阶次幂。
一、希尔排序
希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。
需求：
排序前：{9,1,2,5,7,4,8,6,3,5}
排序后：{1,2,3,4,5,5,6,7,8,9}
二、排序原理
Step1.选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组；
Step2.对分好组的每一组数据完成插入排序；
Step3.减小增长量，最小减为1，重复第二步操作。
API设计
| 类名 | Shell |
| 构造方法 | Shell()：创建Shell对象 |
| 成员方法 | 1.public static void sort(Comparable[] a)：对数组内的元素进行排序 2.private static boolean greater(Comparable v,Comparable w):判断v是否大于w 3.private static void exch(Comparable[] a,int i,int j)：交换a数组中，索引i和索引j处的值 |
1.代码实现
//排序代码 public class Shell { /* 对数组a中的元素进行排序 */ public static void sort(Comparable[] a){ int N = a.length; //确定增长量h的最大值 int h=1; while(h<N/2){ h=h*2+1; } //当增长量h小于1，排序结束 while(h>=1){ //找到待插入的元素 for (int i=h;i<N;i++){ //a[i]就是待插入的元素 //把a[i]插入到a[i-h],a[i-2h],a[i-3h]...序列中 for (int j=i;j>=h;j-=h){ //a[j]就是待插入元素，依次和a[j-h],a[j-2h],a[j-3h]进行比较，如果a[j]小，那么 交换位置，如果不小于，a[j]大，则插入完成。 if (greater(a[j-h],a[j])){ exch(a,j,j-h); }else{ break; } } } h/=2; } } /* 比较v元素是否大于w元素 */ private static boolean greater(Comparable v,Comparable w){ return v.compareTo(w)>0; } /* 数组元素i和j交换位置 */ private static void exch(Comparable[] a,int i,int j){ Comparable t = a[i]; a[i]=a[j]; a[j]=t; } }
测试类
//测试代码 public class Test { public static void main(String[] args) { Integer[] a = {9,1,2,5,7,4,8,6,3,5}; Shell.sort(a); System.out.println("Shell sort " + Arrays.toString(a)); } }
2.运行结果
编写完成之后，点击运行就能知道选择排序的结果，如下图所示：
3.比较希尔排序和插入排序
这里的测试文件JMFive.txt是100000到1倒序的文件，代码如下：
//测试代码 public class SortCompare { public static void main(String[] args) throws Exception{ ArrayList<Integer> list = new ArrayList<>(); //读取reverse_arr.txt文件 BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream("JMFive.txt"))); String line=null; while((line=reader.readLine())!=null){ list.add(Integer.valueOf(line)); } reader.close(); //把集合转换成数组 Integer[] arr = new Integer[list.size()]; list.toArray(arr); testInsertion(arr);//使用插入排序耗时：20859 // testShell(arr);//使用希尔排序耗时：31 } public static void testInsertion(Integer[] arr){ //使用插入排序完成测试 // 1.获取执行之前的时间 long start = System.currentTimeMillis(); // 2.执行算法代码 Insertion.sort(arr); // 3.获取执行之后的时间 long end= System.currentTimeMillis(); // 4.算出程序执行的时间并输出 System.out.println("使用插入排序耗时："+(end-start)); } public static void testShell(Integer[] arr){ //使用希尔排序完成测试 // 1.获取执行之前的时间 long start = System.currentTimeMillis(); // 2.执行算法代码 Shell.sort(arr); // 3.获取执行之后的时间 long end = System.currentTimeMillis(); // 4.算出程序执行的时间并输出 System.out.println("使用希尔排序耗时："+(end-start)); } } }
总结
通过测试发现，在处理大批量数据时，希尔排序的性能确实高于插入排序。
感谢观看，如果有帮助到你，请给题解点个赞和收藏，让更多的人看到。🌹🌹🌹
也欢迎你，关注我。👍👍👍
你们的点赞和留言对我真的很重要！！！ ✿✿✿
