文档章节

ShellSort -- 希尔排序

NinjaFrog
 NinjaFrog
发布于 2017/09/07 23:57
字数 419
阅读 1
收藏 0

/*
 * 希尔排序:先取一个小于n的整数d1作为第一个增量,
 * 把文件的全部记录分成(n除以d1)个组。所有距离为d1的倍数的记录放在同一个组中。
 * 先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,
 * 直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
 */

/*
 * 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序
 * 排序过程:先取一个正整数d1<n,把所有序号相隔d1的数组元素放一组,
 * 组内进行直接插入排序;然后取d2<d1,重复上述分组和排序操作;直至di=1, 即所有记录放进一个组中排序为止
 * 初始:d=5 49 38 65 97 76 13 27 49 55 04
 * 49 13 |-------------------|
 * 38 27     |-------------------|
 * 65 49 |-------------------|
 * 97 55     |-------------------|
 * 76 04 |-------------------|
 * 一趟结果 13 27 49 55 04 49 38 65 97 76
 * d=3 13 27 49  55 04 49 38 65 97 76
 * 13 55 38 76 |------------|------------|------------|
 * 27 04 65 |------------|------------|
 * 49 49 97 |------------|------------|
 * 二趟结果  13 04 49* 38 27 49 55 65 97 76
 * d=1 13 04 49 38 27 49 55 65 97 76
 * |----|----|----|----|----|----|----|----|----| 三趟结果
 * 04 13 27 38 49 49 55 65 76 97
 */

public class ShellSort {
	public static void sort(int[] data) {
		for (int i = data.length / 2; i > 2; i /= 2) {
			for (int j = 0; j < i; j++) {
				insertSort(data, j, i);
			}
		}
		insertSort(data, 0, 1);
	}

	/**
	 * @param data
	 * @param j
	 * @param i
	 */
	private static void insertSort(int[] data, int start, int inc) {
		for (int i = start + inc; i < data.length; i += inc) {
			for (int j = i; (j >= inc) && (data[j] < data[j - inc]); j -= inc) {
				int temp = data[j];
				data[j] = data[j - inc];
				data[j - inc] = temp;
			}
		}
	}
}

 

本文转载自:

共有 人打赏支持
NinjaFrog
粉丝 3
博文 65
码字总数 12838
作品 0
昌平
程序员
私信 提问
常用排序算法(二)

希尔排序 时间复杂度: 空间复杂度: method:将需要排序的的序列划分为若干个较小的序列,对这些序列进行直接插入排序. * 堆排序法 堆是一个完全二叉树,首先 1:将无序的数据构成堆,(既用无序...

eatnothing
2016/02/16
36
0
6种排序算法比较 算法分析

@云中散人 你好,想跟你请教个问题: 源代码是你之前自己写的 十种排序算法比较 这个代码跟我的课程设计题目要求的简直就是一模一样 里面有些问题我不懂 想找你请教一下! 1.里面的希尔算法是...

aalll
2015/12/17
279
5
直接插入排序。冒泡排序。希尔排序。直接选择排序

直接插入排序。冒泡排序。希尔排序。直接选择排序 。 四种排序的总的比较次数和总的移动次数代码的实现 怎么编程(java),, 包括相同的元素。。谢谢各位啊。。。。 基于下面的代码。。 //...

李胜龙
2012/11/30
433
1
算法分析(2)经典排序算法对比

[TOC] 概述 上一篇文章分析了一下基本的排序算法以及Java的实现,不过没有比较深入的去分析,因为对于O(n^2)的算法实现比较简单,但是对于O(nLogn)的算法本身有些复杂,所以就分为两篇文章来...

wustor
2017/11/06
0
0
图书馆刘大妈除了要帮我找对象,还教我排序算法

在图书馆偶遇 快速排序算法 一次关于排序的偶遇 今天,在图书馆发生了一件事。 图书馆书架 新来的志愿者小王被安排将归还的书整理回书架,初次被委派工作的小王瞬间充满热情。然而。。。 面对...

超级数学建模
03/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

设置虚拟机固定IP地址

1、点击虚拟机编辑找到虚拟网络编辑器 2、设置网络 3、修改接口配置文件 切换到cd /etc/sysconfig/network-scripts/下面找到对应接口的文件 添加如下内容 4、修改域名服务器 切换到 vi /etc/...

zhu_kai1
5分钟前
0
0
如何解决分布式系统数据事务一致性问题

一、关于分布式系统事务一致性问题 Java 中有三种可以的事务模型,分别称作本地事务模型(Local Transaction Model),编程式事务模型(Programmatic Transaction Model),和声明式事务模型...

hblt-j
6分钟前
0
0
弹幕,是怎样练成的?

说起弹幕看过视频的都不会陌生,那满屏充满着飘逸评论的效果,让人如痴如醉,无法自拔 最近也是因为在学习关于 canvas 的知识,所以今天就想和大家分享一个关于弹幕的故事 那么究竟弹幕是怎样...

我的卡
8分钟前
0
0
VisualBox 安装 CentOS 7.6 操作记录

20181213 VisualBox 安装 CentOS 7.6 操作记录 1、下载 官网下载地址: https://wiki.centos.org/Download找到i386 Everything (ISO), Minimal (ISO), NetInstall (ISO)选择 阿里云镜......

wwzzhh166
11分钟前
0
0
telegram_bot

new group -> 选择人 -> 填写群名 搜索BotFather -> start =========================== ou can control me by sending these commands: /newbot - create a new bot /mybots - edit your bo......

八戒八戒八戒
20分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部