java中实现希尔排序算法

package Utils.Sort;

/**
 

*希尔排序,要求待排序的数组必须实现Comparable接口
 

*/
 

public class ShellSort implements SortStrategy
 

{
 

private int[] increment;

/**
 

*利用希尔排序算法对数组obj进行排序
 

*/
 

public void sort(Comparable[] obj)
 

{
 

if (obj == null)
 

{
 

throw new NullPointerException("The argument can not be null!");
 

}
 

//初始化步长
 

initGap(obj);
 

//步长依次变化(递减)
 

for (int i = increment.length - 1 ;i >= 0 ;i-- )
 

{
 

int step = increment[i];
 

//由步长位置开始
 

for (int j = step ;j < obj.length ;j++ )
 

{
 

Comparable tmp;
 

//如果后面的小于前面的(相隔step),则与前面的交换
 

for (int m = j ;m >= step ;m = m - step )
 

{
 

if (obj[m].compareTo(obj[m - step]) < 0)
 

{
 

tmp = obj[m - step];
 

obj[m - step] = obj[m];
 

obj[m] = tmp;
 

}

//因为之前的位置必定已经比较过,所以这里直接退出循环
 

else
 

{
 

break;
 

}
 

}
 

}
 

}
 

}
 

/**
 

*根据数组的长度确定求增量的公式的最大指数,公式为pow(4, i) - 3 * pow(2, i) + 1和9 * pow(4, i) - 9 * pow
 

2, i) + 1
 

*@return int[] 两个公式的最大指数
 

*@param length 数组的长度
 

*/
 

private int[] initExponent(int length)
 

{
 

int[] exp = new int[2];
 

exp[0] = 1;
 

exp[1] = -1;
 

int[] gap = new int[2];
 

gap[0] = gap[1] = 0;
 

//确定两个公式的最大指数
 

while (gap[0] < length)
 

{
 

exp[0]++;
 

gap[0] = (int)(Math.pow(4, exp[0]) - 3 * Math.pow(2, exp[0]) + 1);
 

}
 

exp[0]--;
 

while (gap[1] < length)
 

{
 

exp[1]++;
 

gap[1] = (int)(9 * Math.pow(4, exp[1]) - 9 * Math.pow(2, exp[1]) + 1);
 

}
 

exp[1]--;
 

return exp;
 

}

private void initGap(Comparable[] obj)
 

{
 

//利用公式初始化增量序列
 

int exp[] = initExponent(obj.length);
 

int[] gap = new int[2];
 

increment = new int[exp[0] + exp[1]];
 

//将增量数组由大到小赋值
 

for (int i = exp[0] + exp[1] - 1 ;i >= 0 ;i-- )
 

{
 

gap[0] = (int)(Math.pow(4, exp[0]) - 3 * Math.pow(2, exp[0]) + 1);
 

gap[1] = (int)(9 * Math.pow(4, exp[1]) - 9 * Math.pow(2, exp[1]) + 1);
 

//将大的增量先放入增量数组,这里实际上是一个归并排序
 

//不需要考虑gap[0] == gap[1]的情况,因为不可能出现相等。
 

if (gap[0] > gap[1])
 

{
 

increment[i] = gap[0];
 

exp[0]--;
 

}
 

else
 

{
 

increment[i] = gap[1];
 

exp[1]--;
 

}
 

}
 

}
 

}

时间: 2024-12-25 12:27:14

java中实现希尔排序算法的相关文章

【Java】Java中几种排序算法

package javaArray; import java.sql.Date; public class A2 { public static void main(String[] args) { int a[] = new int[5]; Date[] days = new Date[3]; System.out.println(a[3]); System.out.println(days[2]); int[] data = new int[] {3, 9, 2, 8, 7, 0, 4, 6

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

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

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

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

java实现希尔排序算法_java

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

C/C++中的经典排序算法总结

C/C++中的经典排序算法总结 在C/C++中,有一些经典的排序算法,例如:冒泡排序.鸡尾酒排序或双向冒泡排序(改进的冒泡排序).选择排序.直接插入排序.归并排序.快速排序.希尔排序和堆排序等等.下面对这些排序算法进行一一解析并给出示例代码以共享之. 1.冒泡排序 冒泡排序是最基本的排序算法,之所以称之为冒泡排序是因为在冒泡排序的过程中总是大数往前放,小数往后放,相当于气泡上升. 冒泡排序的基本原理是:依次比较相邻的两个数,将大数放在前面,小数放在后面. 影响冒泡排序算法性能的主要部分就是循环和

既然java语言提供了排序算法的封装,为什么我们还要自己写冒泡

问题描述 既然java语言提供了排序算法的封装,为什么我们还要自己写冒泡 一个关于排序的问题:既然java语言提供了排序算法的封装,为什么我们还要自己写冒泡排序?什么时候用到冒泡排序? 解决方案 目的是为了让你学习,冒泡排序是最容易理解的排序算法. 解决方案二: Java语言写的各种排序算法[未完] 解决方案三: java封装好的是快排吧,首先快排是不稳定排序,只是平均时间复杂度最低而已.简单排序中直接插入最好,快速排序最快,当文件为正序时,直接插入和冒泡均最佳.当数据量过大时堆排序的优势又体现

图文讲解Java中实现quickSort快速排序算法的方法_java

相对冒泡排序.选择排序等算法而言,快速排序的具体算法原理及实现有一定的难度.为了更好地理解快速排序,我们仍然以举例说明的形式来详细描述快速排序的算法原理.在前面的排序算法中,我们以5名运动员的身高排序问题为例进行讲解,为了更好地体现快速排序的特点,这里我们再额外添加3名运动员.实例中的8名运动员及其身高信息详细如下(F.G.H为新增的运动员): A(181).B(169).C(187).D(172).E(163).F(191).G(189).H(182) 在前面的排序算法中,这些排序都是由教练主

希尔排序算法的C语言实现示例_C 语言

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本.希尔排序是非稳定排序算法. 希尔排序是基于插入排序的以下两点性质而提出改进方法的: 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位 希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能.这样可以让一个元素可以一次性地朝最终位置前进一大步.然后算法再取越来越小的步长进行排序,算法的最后一步就是普通的插入排序,但是到了这步,需排序的数据几

python实现的希尔排序算法实例

  本文实例讲述了python实现希尔排序算法的方法.分享给大家供大家参考.具体如下: ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 def shellSort(items): inc = len(items) / 2 while inc: for i in xrange(len(items)): j = i temp = items[i] while j >= inc and items[j-inc] > temp: items[j] = items[j - inc]