发布于 2016-07-27 11:24:58 | 109 次阅读 | 评论: 0 | 来源: 网友投递

这里有新鲜出炉的Java函数式编程,程序狗速度看过来!

Java程序设计语言

java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由Sun Microsystems公司于1995年5月推出的Java程序设计语言和Java平台(即JavaEE(j2ee), JavaME(j2me), JavaSE(j2se))的总称。


这篇文章主要介绍了希尔排序算法与相关的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)条评论 发布评论 返回顶部

Copyright © 2007-2017 PHPERZ.COM All Rights Reserved   冀ICP备14009818号  版权声明  广告服务