java数据结构之希尔排序
希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率;
但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。
实现:
先取一个正整数d1 < n, 把所有相隔d1的记录放一组,每个组内进行直接插入排序;然后d2 < d1,重复上述分组和排序操作;直至di = 1,即所有记录放进一个组中排序为止。
简单例子:
import java.util.Arrays; public class Demo4 { public static void main(String[] args) { int old[] = { 2, 5, 3, 8, 6, 9, 4 }; int i,j,temp; int gap = 1; int len = old.length; while (gap < len / 3) { gap = gap * 3 + 1; } for (; gap > 0; gap /= 3) { for (i = gap; i < len; i++) { temp = old[i]; for (j = i - gap; j >= 0 && old[j] > temp; j -= gap) { old[j + gap] = old[j]; } old[j + gap] = temp; } } System.out.println("new:"+Arrays.toString(old)); } }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。
相关推荐
-
Java排序算法总结之希尔排序
本文实例讲述了Java排序算法总结之希尔排序.分享给大家供大家参考.具体分析如下: 前言:希尔排序(Shell Sort)是插入排序的一种.是针对直接插入排序算法的改进.该方法又称缩小增量排序,因DL.Shell于1959年提出而得名.本文主要介绍希尔排序用Java是怎样实现的. 希尔排序(缩小增量法) 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序.希尔排序并不稳定,O(1)的额外空间,时间复杂度为O(N*(logN)^2).最坏的情况下的执行效率和在平均情况下的执行效率相
-
Java实现八个常用的排序算法:插入排序、冒泡排序、选择排序、希尔排序等
本文实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 .快速排序.归并排序.堆排序和LST基数排序 首先是EightAlgorithms.java文件,代码如下: import java.util.Arrays; /* * 实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 * 以及快速排序.归并排序.堆排序和LST基数排序 * @author gkh178 */ public class EightAlgorithms { //插入排序:时间复杂度o(n^2) p
-
java数组排序示例(冒泡排序、快速排序、希尔排序、选择排序)
快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现. 冒泡法是运用遍历数组进行比较,通过不断的比较将最小值或者最大值一个一个的遍历出来. 选择排序法是将数组的第一个数据作为最大或者最小的值,然后通过比较循环,输出有序的数组. 插入排序是选择一个数组中的数据,通过不断的插入比较最后进行排序. 复制代码 代码如下: package com.firewolf.sort; public class MySort { /** * @param args */ public s
-
浅析java 希尔排序(Shell)算法
先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组.所有距离为dl的倍数的记录放在同一个组中.先在各组内进行直接插入排序:然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<:-<d2<d1),即所有记录放在同一组中进行直接插入排序为止. 该方法实质上是一种分组插入方法. 原理图: 源代码 复制代码 代码如下: package com.zc.manythread; /** * * @author 偶my耶 * *
-
java高级排序之希尔排序
希尔排序对于多达几千个数据项的,中等大小规模的数组排序表现良好,希尔排序不像快速排序和其它时间复杂度为O(n*logn)的排序算法那么快,因此,对非常大的文件排序,它不是最优选择,但是希尔排序比选择排序和插入排序这种时间复杂度为O(n²)的排序要快的多,并且它非常容易实现,代码简短 希尔排序也是插入排序的一种,在插入排序中,如果最小的数在最后面,则复制的次数太多,而希尔解决了这个问题,它也是n-增量排序,它的思想是通过加大插入排序中元素的间隔,并在这些有间隔的元素中进行插入排序,当这些数据项排过
-
2个java希尔排序示例
java希尔排序 希尔排序是插入排序的一种类型,也可以用一个形象的叫法缩小增量法.基本思想就是把一个数组分为好几个数组,有点像分治法,不过这里的划分是用一个常量d来控制. 这个0<d<n,n为数组的长度.这个算法有了插入排序的速度,也可以算是一个改进算法,在插入算法中,如果有一个最小的数在数组的最后面,用插入算法就会重最后一个 位置移动到第一个,这样就会浪费很大,使用这个改进的希尔排序可以实现数据元素的大跨度的移动.也就是这个算法的优越之处. 复制代码 代码如下: package cn.cqu
-
用Java实现希尔排序的示例
一.理论准备 希尔排序(Shell Sort)是插入排序的一种,是针对直接插入排序算法的改进,是将整个无序列分割成若干小的子序列分别进行插入排序,希尔排序并不稳定.该方法又称缩小增量排序,因DL.Shell于1959年提出而得名.基本思想:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组.所有距离为d1的倍数的记录放在同一个组中.先在各组内进行直接插入排序:然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<-<d2<
-
细致解读希尔排序算法与相关的Java代码实现
希尔排序(Shell's sort)是一种非常"神奇"的排序算法.说它"神奇",是因为没有任何人能清楚地说明它的性能到底能到什么情况.希尔排序因DL.Shell于1959年提出而得名.自从C. A. R. Hoare在1962年提出快速排序后,由于其更为简单,一般采用快速排序.但是,不少数学家们还是孜孜不倦地寻找希尔排序的最佳复杂度.作为普通程序员,我们可以学习下希尔的思路. 顺便说一句,在希尔排序出现之前,计算机界普遍存在"排序算法不可能突破O(n2)&
-
使用Java实现希尔排序算法的简单示例
简介 希尔排序(缩小增量法) 属于插入类排序,由Shell提出,希尔排序对直接插入排序进行了简单的改进:它通过加大插入排序中元素之间的间隔,并在这些有间隔的元素中进行插入排序,从而使数据项大跨度地移动,当这些数据项排过一趟序之后,希尔排序算法减小数据项的间隔再进行排序,依次进行下去,进行这些排序时的数据项之间的间隔被称为增量,习惯上用字母h来表示这个增量. 常用的h序列由Knuth提出,该序列从1开始,通过如下公式产生: h = 3 * h +1 反过来程序需要反向计算h序列,应该使用 h=(h
-
java实现希尔排序算法
希尔排序算法的基本思想是:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组.所有距离为dl的倍数的记录放在同一个组中.先在各组内进行直接插人排序:然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<-<d2<d1),即所有记录放在同一组中进行直接插入排序为止.该方法实质上是一种分组插入方法. //带增量的插入排序 public static void shellSort(int[] array) { int len =
随机推荐
- Servlet实现文件上传的三种方法总结
- 下拉列表select 由左边框移动到右边示例
- [导入][原创]用脚本控制迅雷下载
- apache服务器一个ip(如:127.0.0.1)和多个域名(虚拟主机)的绑定
- python模拟登录百度代码分享(获取百度贴吧等级)
- 详解javascript高级定时器
- js获取height和width的方法说明
- Sql学习第一天——SQL 将变量定义为Table类型(虚拟表)
- oracle关键字作为字段名使用方法
- Javascript图像处理—平滑处理实现原理
- jQuery 使用手册(六)
- 基于jQuery的倒计时插件代码
- js FLASH幻灯片字符串中有连接符&的处理方法
- JS实现获取剪贴板内容的方法
- C++实现调用系统时间简单示例
- c#与WMI使用技巧集第1/2页
- Bootstrap Chart组件使用教程
- Android仿一点资讯收藏Toast动画效果
- Vue2.0结合webuploader实现文件分片上传功能
- vue生命周期实例小结