`
endual
  • 浏览: 3557537 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

java 希尔排序算法(自己写)

 
阅读更多

希尔排序算法是对插入算法的应用吧,就是多次的使用了插入算法多排序的数组进行排序。

 

1.效率问题

 

   希尔算法的效率到现在还没有理论上的正确答案,但是在实际的测试中的实际复杂度是 N^(3/2)--N^(7/6)之间。空间复杂度是1,它的辅助空间并没有因为数组的大小而改变。

 

2.插入算法的代码

 

    为了清楚的和希尔排序进行比较,先来看下插入算法的排序

     /**

 * 插入排序在大多数的情况是比冒泡算法和选择排序好要的,比冒泡算法要快一倍,比选择排序是快一点
 * 尽管算法比其他的两个要麻烦一点,但是它的想法不复杂,即使它的时间复杂度也是n^2。
 * 插入排序经过被用于在比较复杂的排序算法的最后,快速排序要用到插入排序的
 * ta会出现局部有序,就是在数组的左边的序列是局部的有序的,这样的情况是其他两个没有出现的
 */
	public void sort() {
		
		int out, in ;
        long value = 0l ;
		for (out=1; out < this.nElems-1; out++) { //从1开始,因为第一个已经排序好了的                              
			
			 value = a[out] ;
             in = out ;
             while (in > 0 && a[in] >= value) {
            	 
              a[in] = a[in - 1] ;
              in-- ;
              
             }
             
            a[in] = value ;
              
		}
	}   

 

3.希尔算法的代码

    package endual;

public class ShellSort {

	private long[] theArray ; //待排序的数组
	private int nElems ; //个数
	
	public ShellSort(long[] theArray, int n) {
		
		this.theArray = theArray ;
		this.nElems = n ;
	}
	/**
	 * 打印数列
	 */
	public void displayArray() {
		
		for(int i=0;i<this.theArray.length;i++){
			
			System.out.println(this.theArray[i]);
		}
		
	}
	//下面是希尔算法的排序
	public void shell() {
		
		int inner ;
		int outer ;
		long temp ;
		
		int h = 1 ; //初始的h的值
		while(h <= nElems/3) {
			
			h = h*3 + 1 ;
		}//求出最大的h是多数喽	
			while(h > 0) {
				
				//>>>>>>>>>>>>>>>>>>>>将h改成1那就是插入算法了>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
	
				for(outer = h; outer < this.nElems; outer++) {
					temp = theArray[outer] ;
					inner = outer ;
			
					while(inner > h-1 && theArray[inner-h] >= temp) {
						
						theArray[inner] = theArray[inner-h] ;
						inner = inner - h ;
					
					} // end while
					theArray[inner] = temp ;
					
				} // end for
				//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
				h = (h-1) / 3 ; //然后按照公式将h递减到1形成排序就OK了
				
			} // end whlie (h>0)_

	} //end shell
	
	
}

   测试类代码

package endual;

public class ShellMainApp {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		long[] theArray = {9,32,6,4,2,78,1};
		int n = theArray.length;
		ShellSort ss = new ShellSort(theArray, n) ;
		ss.shell() ;
		ss.displayArray();
	}

}
 

4.希尔算法的一些理论资料

希尔排序是计算机科学家Shell发明的,是基于插入排序的,对插入排序进行改进的。
依靠这个特别的实现机制,希尔排序对于多达几千个数据项,中等大小规模的数组排序表现良好。
希尔排序不像快速排序和归并排序一样,时间复杂度是NlogN的排序算法快,因此对非常大的文件排序并不是最优的选择。
但是希尔排序比选择排序和插入排序这种时间复杂度为N^2的算法速度要快的多了

插入排序:复制的次数太多

插入排序执行到一半的时候,标记符号左边这部分数据项是排序过的,这些数据项中间是有序的,而标记右边的数据项则没有排序过的。
这个算法取出标记符号所指向的数据项,把它存储在一个临时变量里。接着,从刚刚被移除的数据项左边第一个单元开始,每次把有序的
数据项右移动一个单元,直到存储在临时变量里的数据项能够有序回插

插入算法中出现一个特例:
假设一个很小得数据项是很靠近右端位子上,这里本来应该是值比较大的数据项多在的位子。把这个小数据项移动到左边的正确位子上,
所有中间数据项 这个数据项原来所在的位子和它应该移动到位子之间的数据项都必须移动一位。这个步骤对每个数据项都执行了大概N次的复制
虽然不是所有的数据项都要移动N个位子,但是平均移动了N/2次。插入算法的效率是N^2
如果能以一种方式不必一个一个地移动所有中间的数据项,就能把较小的数据项移动到左边。那么这个算法的执行效率就会有很大的改进了

n-增量排序
  希尔排序通过加入插入排序中元素之间的间隔,并在这些有间隔的元素中进行插入排序,从而使数据项能大跨度地移动。
  当这些数据项排过一趟后,希尔排序算法减小数据项的间隔再进行排序,依次进行下去。进行这些排序时数据项之间的间隔被
  称为增量,并且习惯用小写的字母h表示。
  这里的增量是排序数据项的间隔大小,然后对这个间隔的数据项归为一组 对其在数组中进行排序 交换位子
 
 经过这个增量的加入,然后排序过以后,新数列有新的特点了,那就是小的数据是在左边,大的数据是在有边,不大不小的数据是在中间了
 但是没有完全的进行好了排序 。这也是希尔排序的奥秘所在。

插入排序对基本有序的数组是非常有效的,如果插入排序值需要把数据项移动一位或者两位,那么算法大概需要N时间复杂度。当数组完成增量为
4的排序之后,可以进行普通的插入排序。
减小间隔
对于更大的数组,开始的间隔应该大写,然后间隔不断变小,直到间隔为0
举例来说把,对于 含有1000个数据项的数组,可能先以264为增量,然后用121为增量,然后用40为增量,然后用13然后用4最后用1为增量进行希尔排序。
用来间隔的数组成的列称为 间隔数列。
    h = 3*h + 1 (h从1开始)
可以这样来取
排序算法中,首先在一个短小的循环中使用序列的生成公式来计算出最初的间隔。h值最初赋值为1,然后用公式生成4 13 40等等,当间隔
大于数组大小的时候停止h的迭代。
对于含有1000个数据项的,1093就是太大了,那样用364就够了。然后倒即
 

 

 

分享到:
评论

相关推荐

    分别使用Java和Python实现希尔排序算法

    希尔排序:分别使用Java和Python实现希尔排序算法 希尔排序:分别使用Java和Python实现希尔排序算法 希尔排序:分别使用Java和Python实现希尔排序算法 希尔排序:分别使用Java和Python实现希尔排序算法 希尔排序:...

    Java 希尔排序 算法 数据结构 数组 输出

    Java 希尔排序 算法 数据结构 数组 输出

    希尔排序算法Java简单解释

    希尔排序是一种比较实用的排序算法,虽然它不是稳定的排序算法(即相等的元素可能会改变原有的相对顺序),但其效率在许多情况下优于其他简单的排序算法,特别是在处理大规模数据时。在编程实践中,理解并掌握希尔...

    各种排序算法比较(java实现)

    本文将详细探讨标题所提及的几种排序算法:合并排序、插入排序、希尔排序、快速排序、冒泡排序以及桶排序,并结合Java语言的实现进行解析。 1. **合并排序(Merge Sort)**: 合并排序是一种基于分治策略的排序算法...

    详解Java常用排序算法-希尔排序

    希尔排序算法详解 希尔排序(Shell Sort)是一种改进的插入排序算法,它的基本思想是将待排序的数组按照一定的间隔进行分组,对每组使用插入排序算法进行排序,然后缩小间隔,再对分组进行排序,直到间隔为1 为止。...

    Java实现希尔排序算法(源代码)

    ### Java实现希尔排序算法 #### 实现原理 希尔排序(Shell Sort)是插入排序的一种高效改进版本,也称为缩小增量排序。它的基本思想是:先将整个待排序的记录序列分割成为若干子序列(由相隔某个“增量”的记录...

    希尔排序java代码

    希尔排序(Shell Sort)是一种基于插入排序的快速排序算法,由Donald Shell于1959年提出。它的主要思想是将待排序的数据按照一定的增量分组,对每组使用直接插入排序,然后逐渐减小增量,继续进行分组排序,直到增量...

    算法可视化系列——排序算法——希尔排序

    希尔排序(Shell Sort)是一种基于插入排序的快速排序方法,由Donald Shell于1959年提出。它的主要思想是将待排序的数据按照一定的间隔进行分组,然后对每组...对于学习和理解排序算法,希尔排序是不可或缺的一部分。

    常用的排序算法(java实现),附带一个PPT动画演示、详解了其中三种

    这里我们主要关注Java实现的排序算法,并结合一个PPT的动画演示来探讨其中的插入排序、直接插入排序和希尔排序。 首先,让我们深入理解插入排序。插入排序是一种简单的排序算法,其基本思想是将未排序的元素逐个...

    (希尔排序算法).doc计算机系算法分析

    希尔排序是一种基于插入排序的快速排序算法,由Donald Shell于1959年提出。它的主要思想是将待排序的数组元素按照一定的间隔分组,然后对每组进行插入排序,随着间隔逐渐减小,直到间隔为1时,整个数组成为一个组,...

    Java所有排序算法大全

    在编程领域,排序算法是计算机科学中的核心概念,特别是在Java这样的高级编程语言中。本文将深入探讨Java中常见的几种排序算法,包括它们的工作原理、优缺点以及如何在实际编程中应用。 首先,我们来看`BubbleSort...

    希尔排序(java)

    希尔排序(Shell Sort)是一种基于插入排序的快速排序算法,由Donald Shell于1959年提出。它的主要思想是将待排序的数据按照一个增量序列分成若干个子序列,然后分别对子序列进行插入排序,最后再进行一次整体的插入...

    Java各种排序算法代码.

    在编程领域,排序算法是计算机科学中的核心概念,特别是在Java这样的高级编程语言中。排序算法是用来组织和优化数据结构的关键工具,它可以帮助我们快速查找、分析和处理数据。本资源包含的是Java实现的各种常见排序...

    Java各种排序算法_随机数

    Java 排序算法概述 Java 排序算法是指在 Java 编程语言中使用的各种排序方法,旨在对数据进行有序排列。常见的排序算法有插入排序、交换排序、选择排序、归并排序、分配排序等。 插入排序是最基本的一种排序算法,...

    Java常用排序算法源码

    在编程领域,排序算法是计算机科学中的核心概念,特别是在Java这样的高级编程语言中。排序算法是用来组织和优化数据结构的关键工具,使得数据按照特定规则(如升序或降序)排列。以下是对Java中几种常见排序算法的...

    [Java算法-排序]希尔排序.java

    该资源包括实用练习,让读者可以练习在Java中实现希尔排序,并提供解决方案以帮助读者检查自己的工作并深入理解所学内容。 无论您是Java编程的初学者还是有经验的程序员,该资源都将为您提供有价值的指导和支持,...

    JAVA排序算法: 直接插入,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序

    本文将深入探讨Java编程语言中实现的七种主要排序算法:直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序以及归并排序。每种算法都有其独特性,适用于不同的场景和数据特性。 1. **直接插入排序**:...

    JAVA排序算法集合

    根据给定文件的信息,本文将详细介绍Java中的五种主要排序算法:插入排序、交换排序、选择排序、归并排序以及基数排序。每种排序方法都包括了不同的变体和技术细节。 ### 一、插入排序 #### 1. 直接插入排序 直接...

    Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找

    在编程领域,尤其是在Java开发中,排序算法是基础且至关重要的知识。无论是处理数据库查询、数据分析,还是优化程序性能,熟练掌握各种排序算法都显得尤为关键。本资料包聚焦于"Java常用排序算法"和"程序员必须掌握...

Global site tag (gtag.js) - Google Analytics