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));
 }
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • Java实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等

    Java实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等

    本文实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 .快速排序.归并排序.堆排序和LST基数排序 首先是EightAlgorithms.java文件,代码如下: import java.util.Arrays; /* * 实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 * 以及快速排序.归并排序.堆排序和LST基数排序 * @author gkh178 */ public class EightAlgorithms { //插入排序:时间复杂度o(n^2) p

  • 使用Java实现希尔排序算法的简单示例

    简介 希尔排序(缩小增量法) 属于插入类排序,由Shell提出,希尔排序对直接插入排序进行了简单的改进:它通过加大插入排序中元素之间的间隔,并在这些有间隔的元素中进行插入排序,从而使数据项大跨度地移动,当这些数据项排过一趟序之后,希尔排序算法减小数据项的间隔再进行排序,依次进行下去,进行这些排序时的数据项之间的间隔被称为增量,习惯上用字母h来表示这个增量. 常用的h序列由Knuth提出,该序列从1开始,通过如下公式产生: h = 3 * h +1 反过来程序需要反向计算h序列,应该使用 h=(h

  • 细致解读希尔排序算法与相关的Java代码实现

    希尔排序(Shell's sort)是一种非常"神奇"的排序算法.说它"神奇",是因为没有任何人能清楚地说明它的性能到底能到什么情况.希尔排序因DL．Shell于1959年提出而得名.自从C. A. R. Hoare在1962年提出快速排序后,由于其更为简单,一般采用快速排序.但是,不少数学家们还是孜孜不倦地寻找希尔排序的最佳复杂度.作为普通程序员,我们可以学习下希尔的思路. 顺便说一句,在希尔排序出现之前,计算机界普遍存在"排序算法不可能突破O(n2)&

  • java高级排序之希尔排序

    希尔排序对于多达几千个数据项的,中等大小规模的数组排序表现良好,希尔排序不像快速排序和其它时间复杂度为O(n*logn)的排序算法那么快,因此,对非常大的文件排序,它不是最优选择,但是希尔排序比选择排序和插入排序这种时间复杂度为O(n²)的排序要快的多,并且它非常容易实现,代码简短 希尔排序也是插入排序的一种,在插入排序中,如果最小的数在最后面,则复制的次数太多,而希尔解决了这个问题,它也是n-增量排序,它的思想是通过加大插入排序中元素的间隔,并在这些有间隔的元素中进行插入排序,当这些数据项排过

  • 2个java希尔排序示例

    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)算法

    浅析java 希尔排序(Shell)算法

    先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组.所有距离为dl的倍数的记录放在同一个组中.先在各组内进行直接插入排序:然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<:-<d2<d1),即所有记录放在同一组中进行直接插入排序为止. 该方法实质上是一种分组插入方法. 原理图: 源代码 复制代码 代码如下: package com.zc.manythread; /**  *  * @author 偶my耶  *  *

  • Java排序算法总结之希尔排序

    本文实例讲述了Java排序算法总结之希尔排序.分享给大家供大家参考.具体分析如下: 前言:希尔排序(Shell Sort)是插入排序的一种.是针对直接插入排序算法的改进.该方法又称缩小增量排序,因DL．Shell于1959年提出而得名.本文主要介绍希尔排序用Java是怎样实现的. 希尔排序(缩小增量法) 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序.希尔排序并不稳定,O(1)的额外空间,时间复杂度为O(N*(logN)^2).最坏的情况下的执行效率和在平均情况下的执行效率相

  • java数组排序示例(冒泡排序、快速排序、希尔排序、选择排序)

    快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现. 冒泡法是运用遍历数组进行比较,通过不断的比较将最小值或者最大值一个一个的遍历出来. 选择排序法是将数组的第一个数据作为最大或者最小的值,然后通过比较循环,输出有序的数组. 插入排序是选择一个数组中的数据,通过不断的插入比较最后进行排序. 复制代码 代码如下: package com.firewolf.sort; public class MySort { /**  * @param args  */ public s

  • java实现希尔排序算法

    java实现希尔排序算法

    希尔排序算法的基本思想是:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组.所有距离为dl的倍数的记录放在同一个组中.先在各组内进行直接插人排序:然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<-<d2<d1),即所有记录放在同一组中进行直接插入排序为止.该方法实质上是一种分组插入方法. //带增量的插入排序 public static void shellSort(int[] array) { int len =

随机推荐