文档章节

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
博文 61
码字总数 10503
作品 0
昌平
程序员
常用排序算法(二)

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

eatnothing
2016/02/16
36
0
白话经典算法系列之三 希尔排序的实现

希尔排序的实质就是分组插入排序,该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。 该方法的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的...

彭博
2012/04/12
96
0
6种排序算法比较 算法分析

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

aalll
2015/12/17
259
5
白话经典算法系列之三 希尔排序的实现

希尔排序的实质就是分组插入排序,该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。 该方法的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的...

长平狐
2012/12/10
20
0
算法分析(2)经典排序算法对比

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

wustor
2017/11/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

2018资本方向:重新发现社交

2018年可谓是资本寒冬,投资人方面认为今年投资主题较少,大量机构继续项目退出来筹措新一期基金,创业公司上市募资,好让投资人收回资金离场,在如此惨淡的背景下,社交领域的投资却有回暖趋...

ThinkSNS账号
18分钟前
1
0
day118-20181016-英语流利阅读-待学习

耶鲁毕业又如何?美国最高法院大法官被控性侵 雪梨 2018-10-16 1.今日导读 美国最高法院大法官布雷特·卡瓦诺(Brett Kavanaugh)被指涉及 1980 年代多件性侵案,包括克里斯汀·布莱希·福特...

飞鱼说编程
20分钟前
2
0
Android studio取消自动折叠代码

在这里面设置就行

lanyu96
20分钟前
1
0
Magento2后台忘记密码

Magento2后台忘记密码处理方式 第一种(Magento CLI 命令行创建新用户): php bin/magento admin:user:create --admin-user="newName" --admin-password="New-passwd" --admin-email="newN......

alt_tab_jj
21分钟前
1
0
Vue 引入Jquery jQueryRotate.2.2 制作转盘抽奖

原先用jquery做的,现在整合webpack+vue 其实只需要webpack就行了,只是为了方便打包。 1、关闭eslint 检测,如果开启,插件里面全是报错,麻烦的很。 webpack.base.conf.js const createLin...

大灰狼wow
22分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部