文档章节

ShellSort -- 希尔排序

gackey
 gackey
发布于 2017/09/07 23:57
字数 505
阅读 3
收藏 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;
			}
		}
	}
}

 

© 著作权归作者所有

gackey

gackey

粉丝 4
博文 77
码字总数 22015
作品 0
昌平
程序员
私信 提问
加载中

评论(0)

10-5-希尔排序-内部排序-第10章-《数据结构》课本源码-严蔚敏吴伟民版

课本源码部分 第10章 内部排序 - 希尔排序 ——《数据结构》-严蔚敏.吴伟民版 源码使用说明 链接☛☛☛ 《数据结构-C语言版》(严蔚敏,吴伟民版)课本源码+习题集解析使用说明 课本源码合辑 ...

康建伟
2016/06/22
0
0
612.1.004 ALGS4 | Elementary Sorts - 基础排序算法

sublime编辑器写代码,命令行编译减少对ide的依赖//可以提示缺少什么依赖import所有示例代码动手敲一遍Graham's Scan是经典的计算几何算法shffule 与 map-reduce 有关—— 云计算知道这些算法...

osc_65e48kpp
2019/03/11
2
0
常用排序算法(二)

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

eatnothing
2016/02/16
39
0
好程序员Java学习路线带你5分钟了解希尔排序

好程序员Java学习路线带你5分钟了解希尔排序,前言:希尔排序(shell sort)是插入排序的一种,它是简单插入排序经过改进之后的一个更高效的算法,这个排序方法又称为缩小增量排序。 希尔排序...

好程序员IT
2019/07/18
34
0
6种排序算法比较 算法分析

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

aalll
2015/12/17
292
5

没有更多内容

加载失败,请刷新页面

加载更多

Entity Framework Core配置DbContext的两种方式

Entity Framework Core配置DbContext的两种方式 使用Entity Framework迁移过程中遇到过一个问题,在这里拿出来晒晒。 Unable to create an object of type 'xxxContext'. For the different......

osc_9twbv6jz
28分钟前
18
0
layui结构

layui 静态资源 src/layuiadmin/:layuiAdmin 的静态资源(JS、CSS、模块碎片等)

申光跃喝大米汤
28分钟前
25
0
算法分享之关于atcoderbeginner166E的讲解

序言:博客是为了别人写?还是自己写。在我看来,博客可以帮助我记录自己的知识的欢愉,以别人的角度去审视自己的想法,博客帮助我记录自己的成长,也等待着一位位有缘人。 好了,不多说了,...

osc_8rbrmk98
29分钟前
18
0
Visual Studio之重构(二)

学习网址:https://docs.microsoft.com/zh-cn/visualstudio/get-started/visual-studio-ide?view=vs-2019 示范 vs2019: 变量的重命名的重构,更改该变量命名的同时,引用该变量的地方也会更...

osc_dc6pbw3x
30分钟前
17
0
人工智能的四个核心能力是语音、图像、自然语言理解和用户画像(主要应用领域)

转自:https://www.leiphone.com/news/201609/RqBizumSAK82B1Dj.html https://www.sohu.com/a/252300234_99924609...

osc_nc5ghpm9
31分钟前
28
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部