本文主要是介绍Java 希尔排序算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
简介
上一章我们学习了 Java 插入排序算法,这一章,我们来学习插入排序算法,so,多了不说,继续老规矩,学习内容如下:
1、希尔排序的定义
2、希尔排序的思路
3、代码实现
1.希尔排序的定义
希尔排序的实质就是:分组插入排序,它是简单插入排序经过改进之后的一个更高效的版本,又称缩小增量法。
将整个无序序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序时,再对全体元素进行一次直接插入排序。
因为直接插入排序在元素基本有序的情况下,效率是很高的,因此希尔排序在时间效率上有很大提高。
2.希尔排序的思路
简单的插入排序
- 默认从第2个数据开始比较。如果第2个数据比第1个小,则交换。
- 然后在用第3个数据比较,如果比前面小,则插入。否则,退出循环。
- 说明:默认将第1数据看成有序列表,后面无序的列表循环每一个数据,如果比前面的数据小则插入(交换)。否则退出。
希尔排序
- 基本上和插入排序一样的道理
- 不一样的地方在于,每次循环的步长,通过减半的方式来实现
- 说明:基本原理和插入排序类似,不一样的地方在于。通过间隔多个数据来进行插入排序。
3.代码实现
package com.gongchao.boss;/*** description: 希尔排序* auth: zengtao* time: 2020-12-11 15:45**/
public class Main {public static void main(String[] args) {int arr[] = {9, 5, 2, 7, 4};// 希尔排序sortHill(arr);}private static void sortHill(int[] arr) {// 希尔排序for (int i = arr.length / 2; i > 0; i /= 2) {// i层循环控制步长for (int j = i; j < arr.length; j++) {// j控制无序端的起始位置for (int k = j; k > 0 && k - i >= 0; k -= i) {if (arr[k] < arr[k - i]) {int temp = arr[k - i];arr[k - i] = arr[k];arr[k] = temp;} else {break;}// 打印排序后的数据systemArr(arr);}}// j,k为插入排序,不过步长为i}}private static void systemArr(int[] arr) {for (int i : arr) {System.out.print(i + " ");}System.out.println("");}
}
运行结果
而一般的插入排序运行结果如下
两者对比:希尔排序,时间上很明显高效了很多 实际情况也证明了,希尔排序是高效的,大大的节约了时间
我也查阅了很多资料和文献,有这么一个说法
PS:当需要插入的数是较小的数时,后移的次数明显增多,对效率会有影响
我这边也测试了下
测试数据 { 2,3,4,5,6,1}
运行结果
同样5个数据的情况下,链路和步的确有所拉长,也可能数据太少,不够明显,但是这个说法的确是正确的。
好了
到此为止,希尔排序已经总结完毕。
欢迎观看,Thanks !
这篇关于Java 希尔排序算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!