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

希尔排序(Shell's sort)是一种非常“神奇”的排序算法。说它“神奇”,是因为没有任何人能清楚地说明它的性能到底能到什么情况。希尔排序因DL.Shell于1959年提出而得名。自从C. A. R. Hoare在1962年提出快速排序后,由于其更为简单,一般采用快速排序。但是,不少数学家们还是孜孜不倦地寻找希尔排序的最佳复杂度。作为普通程序员,我们可以学习下希尔的思路。
顺便说一句,在希尔排序出现之前,计算机界普遍存在“排序算法不可能突破O(n2)”的观点。希尔排序的出现打破了这个魔咒,很快,快速排序等算法相继问世。从这个意义上说,希尔排序带领我们走向了一个新的时代。

算法概述/思路
希尔排序的提出,主要基于以下两点:
1.插入排序算法在数组基本有序的情况下,可以近似达到O(n)复杂度,效率极高。
2.但插入排序每次只能将数据移动一位,在数组较大且基本无序的情况下性能会迅速恶化。

基于此,我们可以使用一种分组的插入排序方法,具体做法是:(以一个16元素大小的数组为例)
1.选择一个增量delta,该增量大于1,从数组中按此增量选择出子数组进行一次直接插入排序。例如,若选择增量为5,则对下标为0,5,10,15的元素进行排序。
2.保留该增量delta并依次移动首个元素进行直接插入排序,直到一轮完成。对于上面的例子,则依次对数组[1,6,11],[2,7,12],[3,8,13],[4,9,14]进行排序。
3.减小增量,不断重复上述过程,直到增量减小为1.显然,最后一次为直接插入排序。
4.排序完成。
从上面可以看出,增量是不断减小的,因此,希尔排序又被成为“缩小增量排序”。

代码实现

package sort; 

public class ShellSortTest {
  public static int count = 0; 

  public static void main(String[] args) { 

    int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
    print(data);
    shellSort(data);
    print(data); 

  } 

  public static void shellSort(int[] data) {
    // 计算出最大的h值
    int h = 1;
    while (h <= data.length / 3) {
      h = h * 3 + 1;
    }
    while (h > 0) {
      for (int i = h; i < data.length; i += h) {
        if (data[i] < data[i - h]) {
          int tmp = data[i];
          int j = i - h;
          while (j >= 0 && data[j] > tmp) {
            data[j + h] = data[j];
            j -= h;
          }
          data[j + h] = tmp;
          print(data);
        }
      }
      // 计算出下一个h值
      h = (h - 1) / 3;
    }
  } 

  public static void print(int[] data) {
    for (int i = 0; i < data.length; i++) {
      System.out.print(data[i] + "\t");
    }
    System.out.println();
  } 

}

运行结果:

5  3  6  2  1  9  4  8  7
1  3  6  2  5  9  4  8  7
1  2  3  6  5  9  4  8  7
1  2  3  5  6  9  4  8  7
1  2  3  4  5  6  9  8  7
1  2  3  4  5  6  8  9  7
1  2  3  4  5  6  7  8  9
1  2  3  4  5  6  7  8  9

算法性能/复杂度
希尔排序的增量数列可以任取,需要的唯一条件是最后一个一定为1(因为要保证按1有序)。但是,不同的数列选取会对算法的性能造成极大的影响。上面的代码演示了两种增量。
切记:增量序列中每两个元素最好不要出现1以外的公因子!(很显然,按4有序的数列再去按2排序意义并不大)。
下面是一些常见的增量序列。
第一种增量是最初Donald Shell提出的增量,即折半降低直到1。据研究,使用希尔增量,其时间复杂度还是O(n2)。
第二种增量Hibbard:{1, 3, ..., 2^k-1}。该增量序列的时间复杂度大约是O(n^1.5)。
第三种增量Sedgewick增量:(1, 5, 19, 41, 109,...),其生成序列或者是9*4^i - 9*2^i + 1或者是4^i - 3*2^i + 1。

算法稳定性
我们都知道插入排序是稳定算法。但是,Shell排序是一个多次插入的过程。在一次插入中我们能确保不移动相同元素的顺序,但在多次的插入中,相同元素完全有可能在不同的插入轮次被移动,最后稳定性被破坏,因此,Shell排序不是一个稳定的算法。

算法适用场景
Shell排序虽然快,但是毕竟是插入排序,其数量级并没有后起之秀--快速排序O(n㏒n)快。在大量数据面前,Shell排序不是一个好的算法。但是,中小型规模的数据完全可以使用它。

(0)

相关推荐

  • java实现希尔排序算法

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

  • 2个java希尔排序示例

    java希尔排序 希尔排序是插入排序的一种类型,也可以用一个形象的叫法缩小增量法.基本思想就是把一个数组分为好几个数组,有点像分治法,不过这里的划分是用一个常量d来控制. 这个0<d<n,n为数组的长度.这个算法有了插入排序的速度,也可以算是一个改进算法,在插入算法中,如果有一个最小的数在数组的最后面,用插入算法就会重最后一个 位置移动到第一个,这样就会浪费很大,使用这个改进的希尔排序可以实现数据元素的大跨度的移动.也就是这个算法的优越之处. 复制代码 代码如下: package cn.cqu

  • java高级排序之希尔排序

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

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

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

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

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

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

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

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

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

  • 用Java实现希尔排序的示例

    一.理论准备 希尔排序(Shell Sort)是插入排序的一种,是针对直接插入排序算法的改进,是将整个无序列分割成若干小的子序列分别进行插入排序,希尔排序并不稳定.该方法又称缩小增量排序,因DL.Shell于1959年提出而得名.基本思想:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组.所有距离为d1的倍数的记录放在同一个组中.先在各组内进行直接插入排序:然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<-<d2<

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

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

  • Java经典排序算法之希尔排序详解

    一.希尔排序(Shell Sort) 希尔排序(Shell Sort)是一种插入排序算法,因D.L.Shell于1959年提出而得名. Shell排序又称作缩小增量排序. 二.希尔排序的基本思想 希尔排序的中心思想就是:将数据进行分组,然后对每一组数据进行排序,在每一组数据都有序之后,就可以对所有的分组利用插入排序进行最后一次排序.这样可以显著减少交换的次数,以达到加快排序速度的目的. 希尔排序的中心思想:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组.所有距离为dl的倍数

随机推荐