发布于 2016-07-27 09:54:48 | 189 次阅读 | 评论: 0 | 来源: 网友投递

这里有新鲜出炉的Java并发编程示例,程序狗速度看过来!

Java程序设计语言

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


这篇文章主要介绍了使用Java实现希尔排序算法的简单示例,希尔排序可以被看作是插入排序的一种更高效的改进版本,需要的朋友可以参考下

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


h = 3 * h +1

反过来程序需要反向计算h序列,应该使用


h=(h-1)/3

代码实现
实现代码1:


public static void shellSort(int[] arr){
  int temp;
  for (int delta = arr.length/2; delta>=1; delta/=2){               //对每个增量进行一次排序
    for (int i=delta; i<arr.length; i++){       
      for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){ //注意每个地方增量和差值都是delta
        temp = arr[j-delta];
        arr[j-delta] = arr[j];
        arr[j] = temp;
      }
    }//loop i
  }//loop delta
}

实现代码2:


public static void shellSort2(int[] arr){
  int delta = 1;
  while (delta < arr.length/3){//generate delta
    delta=delta*3+1;  // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
  }    
  int temp;
  for (; delta>=1; delta/=3){
    for (int i=delta; i<arr.length; i++){       
      for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){
        temp = arr[j-delta];
        arr[j-delta] = arr[j];
        arr[j] = temp;
      }
    }//loop i
  }//loop delta
}

上面程序在和直接插入法比较,会发现其与直接插入排序的差别在于:直接插入排序中的h会以1代替。
Shell排序是不稳定的,它的空间开销也是O(1),时间开销估计在O(N3/2)~O(N7/6)之间。



最新网友评论  共有(0)条评论 发布评论 返回顶部

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