文档章节

ShellSort -- 希尔排序

garkey
 garkey
发布于 2017/09/07 23:57
字数 419
阅读 1
收藏 0
点赞 0
评论 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;
			}
		}
	}
}

 

本文转载自:

共有 人打赏支持
garkey
粉丝 3
博文 58
码字总数 8942
作品 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
图书馆刘大妈除了要帮我找对象,还教我排序算法

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

超级数学建模
03/08
0
0
几种常见排序算法

几种常见排序算法 标签: algorithms [TOC] 本文介绍几种常见排序算法(选择排序,插入排序,希尔排序,归并排序,快速排序,堆排序),对算法的思路、性质、特点、具体步骤、java实现以及t...

brianway
2016/05/08
133
2
Java 常用排序算法实现--快速排序、插入排序、选择、冒泡

public class ArrayOperation { //二分查找算法 public static int branchSearch(int[] array, int searchNum) { if (array == null) throw new NullPointerException("Null Referrence"); i......

商者
2016/03/28
84
0
Java数据结构与算法(六)-希尔排序

一、希尔排序的产生 希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名...

FantJ
2017/12/21
0
0
基本数据结构之Sort

问题描述: BubbleSort InsertionSort ShellSort MergeSort HeapSort QuickSort 问题分析: 时间复杂度? 空间复杂度? 代码实现: public class BubbleSort { public static <AnyType extends......

关西大汉弹琵琶
2015/10/25
148
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

idea tomcat 远程调试

tomcat 配置 编辑文件${tomcat_home}/bin/catalina.sh,在文件开头添加如下代码。    CATALINA_OPTS="-Xdebug -Xrunjdwp:transport=dt_socket,server=y,suspend=n,address=7829" Idea端配......

qwfys
今天
1
0
遍历目录下的文件每250M打包一个文件

#!/usr/bin/env python # -*- utf-8 -*- # @Time : 2018/7/20 0020 下午 10:16 # @Author : 陈元 # @Email : abcmeabc@163.com # @file : tarFile.py import os import tarfile import thr......

寻爱的小草
今天
1
0
expect同步文件&expect指定host和要同步的文件&构建文件分发系统&批量远程执行命令

20.31 expect脚本同步文件 expect通过与rsync结合,可以在一台机器上把文件自动同步到多台机器上 编写脚本 [root@linux-5 ~]# cd /usr/local/sbin[root@linux-5 sbin]# vim 4.expect#!/...

影夜Linux
今天
1
0
SpringBoot | 第九章:Mybatis-plus的集成和使用

前言 本章节开始介绍数据访问方面的相关知识点。对于后端开发者而言,和数据库打交道是每天都在进行的,所以一个好用的ORM框架是很有必要的。目前,绝大部分公司都选择MyBatis框架作为底层数...

oKong
今天
12
0
win10 上安装解压版mysql

1.效果 2. 下载MySQL 压缩版 下载地址: https://downloads.mysql.com/archives/community/ 3. 配置 3.1 将下载的文件解压到合适的位置 我最终将myql文件 放在:D:\develop\mysql 最终放的位...

Lucky_Me
今天
2
0
linux服务器修改mtu值优化cpu

一、jumbo frames 相关 1、什么是jumbo frames Jumbo frames 是指比标准Ethernet Frames长的frame,即比1518/1522 bit大的frames,Jumbo frame的大小是每个设备厂商规定的,不属于IEEE标准;...

问题终结者
今天
2
0
expect脚本同步文件expect脚本指定host和要同步的文件 构建文件分发系统批量远程执行命令

expect脚本同步文件 在一台机器上把文件同步到多台机器上 自动同步文件 vim 4.expect [root@yong-01 sbin]# vim 4.expect#!/usr/bin/expectset passwd "20655739"spawn rsync -av ro...

lyy549745
今天
1
0
36.rsync下 日志 screen

10.32/10.33 rsync通过服务同步 10.34 linux系统日志 10.35 screen工具 10.32/10.33 rsync通过服务同步: rsync还可以通过服务的方式同步。那需要开启一个服务,他的架构是cs架构,客户端服务...

王鑫linux
今天
1
0
matplotlib 保存图片时的参数

简单绘图 import matplotlib.pyplot as pltplt.plot(range(10)) 保存为csv格式,放大后依然很清晰 plt.savefig('t1.svg') 普通保存放大后会有点模糊文件大小20多k plt.savefig('t5.p...

阿豪boy
今天
3
0
java 8 复合Lambda 表达式

comparator 比较器复合 //排序Comparator.comparing(Apple::getWeight);List<Apple> list = Stream.of(new Apple(1, "a"), new Apple(2, "b"), new Apple(3, "c")) .collect(......

Canaan_
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部