这篇文章主要介绍了浅析java 希尔排序(Shell)算法的原理以及示例，需要的朋友可以参考下
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<；…<d2<d1），即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。
原理图：
源代码
代码如下:
package com.zc.manythread;
/**
*
* @author 偶my耶
*
*/
public class ShellSort {
public static int count = 0;
public static void shellSort(int[] data) {
// 计算出最大的h值
int h = 1;
while (h <= data.length / 3) {
h = h * 3 + 来源gao@daima#com搞(%代@#码网1;
}
while (h > 0) {
for (int i = h; i <data.length; i += h) {
if (data[i] <data[i – h]) {
int tmp = data[i];
int j = i – h;
while (j >= 0 && data[j] > tmp) {
data[j + h] = data[j];
j -= h;
}
data[j + h] = tmp;
print(data);
}
}
// 计算出下一个h值
h = (h – 1) / 3;
}
}
public static void print(int[] data) {
for (int i = 0; i <data.length; i++) {
System.out.print(data[i] + “\t”);
}
System.out.println();
}
public static void main(String[] args) {
int[] data = new int[] { 4, 3, 6, 2, 1, 9, 5, 8, 7 };
print(data);
shellSort(data);
print(data);
}
}
/**
*
* @author 偶my耶
*
*/
public class ShellSort {
public static int count = 0;
public static void shellSort(int[] data) {
// 计算出最大的h值
int h = 1;
while (h <= data.length / 3) {
h = h * 3 + 来源gao@daima#com搞(%代@#码网1;
}
while (h > 0) {
for (int i = h; i <data.length; i += h) {
if (data[i] <data[i – h]) {
int tmp = data[i];
int j = i – h;
while (j >= 0 && data[j] > tmp) {
data[j + h] = data[j];
j -= h;
}
data[j + h] = tmp;
print(data);
}
}
// 计算出下一个h值
h = (h – 1) / 3;
}
}
public static void print(int[] data) {
for (int i = 0; i <data.length; i++) {
System.out.print(data[i] + “\t”);
}
System.out.println();
}
public static void main(String[] args) {
int[] data = new int[] { 4, 3, 6, 2, 1, 9, 5, 8, 7 };
print(data);
shellSort(data);
print(data);
}
}
运行结果:
Shell排序是不稳定的，它的空间开销也是O(1),时间开销估计在O(N3/2)~O(N7/6)之间
以上就是浅析java 希尔排序(Shell)算法的详细内容，更多请关注gaodaima搞代码网其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：浅析java 希尔排序(Shell)算法
转载请注明原文链接：浅析java 希尔排序(Shell)算法
