首页 > 代码库 > Shell排序(希尔)算法--java
Shell排序(希尔)算法--java
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<；…<d2<d1），即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。
原理图：
源代码
1 package com.zc.manythread; 2 /** 3 * 4 * @author 偶my耶 5 * 6 */ 7 public class ShellSort { 8 public static int count = 0; 9 10 public static void shellSort(int[] data) {11 // 计算出最大的h值12 int h = 1;13 while (h <= data.length / 3) {14 h = h * 3 + 1;15 }16 while (h > 0) {17 for (int i = h; i < data.length; i += h) {18 if (data[i] < data[i - h]) {19 int tmp = data[i];20 int j = i - h;21 while (j >= 0 && data[j] > tmp) {22 data[j + h] = data[j];23 j -= h;24 }25 data[j + h] = tmp;26 print(data);27 }28 }29 // 计算出下一个h值30 h = (h - 1) / 3;31 }32 }33 34 public static void print(int[] data) {35 for (int i = 0; i < data.length; i++) {36 System.out.print(data[i] + "\t");37 }38 System.out.println();39 }40 public static void main(String[] args) {41 42 int[] data = http://www.mamicode.com/new int[] { 4, 3, 6, 2, 1, 9, 5, 8, 7 };43 print(data);44 shellSort(data);45 print(data);46 47 }48 }
运行结果:
Shell排序是不稳定的，它的空间开销也是O(1),时间开销估计在O(N3/2)~O(N7/6)之间
Shell排序(希尔)算法--java
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。