首页 > 代码库 > 常用算法Java实现之希尔排序
常用算法Java实现之希尔排序
希尔排序严格来说是基于插入排序的思想，又被称为缩小增量排序。
具体流程如下：
1、将包含n个元素的数组，分成n/2个数组序列，第一个数据和第n/2+1个数据为一对...
2、对每对数据进行比较和交换，排好顺序；
3、然后分成n/4个数组序列，再次排序；
4、不断重复以上过程，随着序列减少并直至为1，排序完成。
假如有初始数据：25 11 45 26 12 78。
1、第一轮排序，将该数组分成 6/2=3 个数组序列，第1个数据和第4个数据为一对，第2个数据和第5个数据为一对，第3个数据和第6个数据为一对，每对数据进行比较排序，排序后顺序为：[25, 11, 45, 26, 12, 78]。
2、第二轮排序 ，将上轮排序后的数组分成6/4=1个数组序列，此时逐个对数据比较，按照插入排序对该数组进行排序，排序后的顺序为：[11, 12, 25, 26, 45, 78]。
对于插入排序而言，如果原数组是基本有序的，那排序效率就可大大提高。另外，对于数量较小的序列使用直接插入排序，会因需要移动的数据量少，其效率也会提高。因此，希尔排序具有较高的执行效率。
希尔排序并不稳定，O(1)的额外空间，时间复杂度为O(N*(logN)^2)。
Java 代码实现如下：（https://github.com/xbk417/algorithm）
1 public void sort(int[] arr) { 2 // i表示希尔排序中的第n/2+1个元素（或者n/4+1） 3 // j表示希尔排序中从0到n/2的元素（n/4） 4 // r表示希尔排序中n/2+1或者n/4+1的值 5 int i, j, r, tmp; 6 // 划组排序 7 for(r = arr.length / 2; r >= 1; r = r / 2) { 8 for(i = r; i < arr.length; i++) { 9 tmp = arr[i];10 j = i - r;11 // 一轮排序12 while(j >= 0 && tmp < arr[j]) {13 arr[j+r] = arr[j];14 j -= r;15 }16 arr[j+r] = tmp;17 }18 System.out.println(i + ":" + Arrays.toString(arr));19 }20 }
常用算法Java实现之希尔排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。