时间:2021-05-19
先取一个小于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 + 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)之间
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
一、希尔排序(ShellSort)希尔排序(ShellSort)是一种插入排序算法,因D.L.Shell于1959年提出而得名。Shell排序又称作缩小增量排序
希尔排序(Shell'ssort)是一种非常“神奇”的排序算法。说它“神奇”,是因为没有任何人能清楚地说明它的性能到底能到什么情况。希尔排序因DL.Shell于
本文实例讲述了Java排序算法总结之希尔排序。分享给大家供大家参考。具体分析如下:前言:希尔排序(ShellSort)是插入排序的一种。是针对直接插入排序算法的
C++算法之希尔排序算法详解及实例希尔排序算法定义:希尔排序是插入排序的一种,也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。算法思想:希尔排序是把
本文实例讲述了java数据结构与算法之希尔排序。分享给大家供大家参考,具体如下:这里要介绍的是希尔排序(缩小增量排序法)。希尔排序:通过比较相距一定间隔的元素来