2个java希尔排序示例

java希尔排序

希尔排序是插入排序的一种类型，也可以用一个形象的叫法缩小增量法。基本思想就是把一个数组分为好几个数组，有点像分治法，不过这里的划分是用一个常量d来控制。

这个0<d<n,n为数组的长度。这个算法有了插入排序的速度，也可以算是一个改进算法，在插入算法中，如果有一个最小的数在数组的最后面，用插入算法就会重最后一个

位置移动到第一个，这样就会浪费很大，使用这个改进的希尔排序可以实现数据元素的大跨度的移动。也就是这个算法的优越之处。

代码如下:

package cn.cqu.coce.xutao;

public class shell3 {
 public static void main(String args[]){
  int a[]={7,43,23,5,3,2,0,6,74,9};
  int n=a.length;
  for(int i=0;i<n;i++)
   System.out.print(a[i]+"\t");
  System.out.println();
     for(int gap=n/2;gap>0;gap/=2){
      for(int i=gap;i<n;i++){
       for(int j=i-gap;j>=0&&a[j]>a[j+gap];j-=gap){
        int temp=a[j+gap];
        a[j+gap]=a[j];
        a[j]=temp;
       }
      }
     }
  for(int i=0;i<n;i++)
   System.out.print(a[i]+"\t");
  System.out.println();
 }
}

第二个示例



代码如下:

class Shell
{
    public void shell_sort(int [] arrays){
        for(int d=5;d>0;d=d-2){
            for(int c=0;c<arrays.length-d;c++){
                for(int i=c;i<arrays.length;i=i+d){
                    for(int j=i;j>0;j=j-d){
                        if(j<d)
                            break;
                        if(arrays[j]<arrays[j-d]){
                            int tmp;
                            tmp=arrays[j];
                            arrays[j]=arrays[j-d];
                            arrays[j-d]=tmp;

}
                    }
                }

}
            snp(arrays);
        }

}
    public void snp(int[] arrays){
        for(int i=0;i<arrays.length;i++){
            System.out.print(arrays[i]+" ");

}
        System.out.println();
    }
    public static void main(String[] args)
    {
        Shell s=new Shell();
        int[] a={45,20,80,40,26,58,66,70};
        s.shell_sort(a);

}
}

运行结果：


代码如下:

---------- java ----------
20 70 40 26 58 66 80
20 58 45 26 70 66 80
26 40 45 58 66 70 80

输出完成 (耗时 0 秒) - 正常终止

赞 (0)

相关推荐

  • java高级排序之希尔排序

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

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

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

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

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

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

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

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

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

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

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

  • java 中基本算法之希尔排序的实例详解

    java 中基本算法之希尔排序的实例详解 希尔排序(Shell Sort)是插入排序的一种.也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本.希尔排序是非稳定排序算法.该方法因DL．Shell于1959年提出而得名. 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序:随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止. 基本思想:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差

  • 2个java希尔排序示例

    2个java希尔排序示例

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

  • Go语言数据结构之希尔排序示例详解

    Go语言数据结构之希尔排序示例详解

    目录 希尔排序 算法思想 图解算法 Go 代码实现: 总结 希尔排序 在插入排序中,在待排序序列的记录个数比较少,而且基本有序,则排序的效率较高. 1959 年,Donald Shell 从“减少记录个数” 和 “基本有序” 两个方面对直接插入排序进行了改进,提出了希尔排序算法. 希尔排序又称为“缩小增量排序”.即将待排序记录按下标的一定增量分组(减少记录个数),对每组记录使用直接插入排序算法排序(达到基本有序): 随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1,整个序列基本有序,再对

  • 排序算法图解之Java希尔排序

    目录 1.希尔排序简介 2.希尔排序算法图解 3.希尔排序代码实现 1.希尔排序简介 希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法,其也是一种特殊的插入排序,即将简单的插入排序进行改进后的一个更加高效的版本,也称缩小增量排序. 希尔排序是非稳定排序算法.把记录按下标的一定增量分组,对每组使用直接插入排序算法排序:随着增量逐渐减少,每组包含的关键词越来越多,当增量减至 1 时,整个文件恰被分成一组,算法便终止. 2.希尔排序算法图解 以序列: {8, 9, 1, 7,

  • java实现希尔排序算法

    java实现希尔排序算法

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

  • 图解Java经典算法希尔排序的原理与实现

    目录 希尔排序 算法思想 图解 代码实现(Java) 希尔排序 希尔排序时插入排序的一种,也称缩小增量排序,是直接插入排序的一种更高效的改进版本.希尔排序是非稳定排序算法. 算法思想 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序,随着增量逐渐减少,每组包含的数越来越多当增量减至1时,整个序列恰好被分成一组,算法完成. 我们以增序排序为例,希尔排序基本步骤:选择初始增量gap=length/2,缩小增量继续以gap=gap/2的方式进行,直到增量gap=1为止,增量的每次变

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

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

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

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

  • Java 选择排序、插入排序、希尔算法实例详解

    Java 选择排序、插入排序、希尔算法实例详解

    1.基本思想: 在要排序的一组数中,选出最小的一个数与第一个位置的数交换:然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止. 2.实例 3.算法实现 /** * 选择排序算法 * 在未排序序列中找到最小元素,存放到排序序列的起始位置 * 再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾. * 以此类推,直到所有元素均排序完毕. * @param numbers */ public static void selectSort(int[] nu

随机推荐