精华内容
下载资源
问答
  • java实现希尔排序算法

    2020-09-03 20:00:45
    希尔排序(Shell Sort)是插入排序的一种,是针对直接插入排序算法的改进,是将整个无序列分割成若干小的子序列分别进行插入排序,希尔排序并不稳定。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。
  • 主要介绍了使用Java实现希尔排序算法的简单示例,希尔排序可以被看作是插入排序的一种更高效的改进版本,需要的朋友可以参考下
  • 希尔排序是首个O(n^2)的排序算法,他是对前面说到的插入排序的改进版。下面就来看看它究竟是怎么进行排序的吧。 希尔排序就是先定义一个增量,然后根据这个增量将几个元素分成一组,最终可能会得到很多个组,在组...

    导航:

            希尔排序是首个时间复杂度突破O(n^2)的排序算法,它是对前面说到的插入排序的改进版。下面就来看看它究竟是怎么进行排序的吧。

            希尔排序就是先定义一个增量,然后根据这个增量将几个元素分成一组,最终可能会得到很多个组,在组内进行插入排序,每个组都完成排序后再缩小增量,再排序,直到增量为1,也就是所有排序都成为了一组,这个时候就变成了最简单的插入排序了。

            接合图来将,第一遍,84,50为一组,83,70为一组,88,60为一组,87,80为一组,61,99为一组,然后在组内进行插入排序。第二遍50,60,61,83,87为一组,70,80,84,88,99为一组,然后进行插入排序,第三遍所有元素为一组,进行插入排序。

            比较前面讲到的插入排序算法,插入排序算法有可能会遇到一个非常坏的情况,就是数组末尾的元素是一个非常小的数,他要进行插入就要逐个比较相邻的元素,如果这个数组非常长,那么就要比较很多次了,而希尔排序减少了这种可能,数组末尾比较小的数在增量比较大的时候就已经插入到前面去了,所以希尔排序比传统的插入排序更快!

    代码实现:

    public class ShellSort {
        public static void main(String[] args) {
            //定义数组
            int[] arr = {99, 55, 2, 3, 9, 10, 22, 34, 67, 89, 69, 92, 101, 102};
            //增量
            int gap = arr.length;
            //排序
            sort(arr, gap);
            for (int i = 0; i < arr.length; i++) {
                System.out.println(arr[i]);
            }
        }
    
        public static void sort(int[] arr, int gap) {
            //确定新一轮分组的增量
            gap = gap / 2;
            //对数组进行分组
            for (int i = 0; i < gap; i++) {
                for (int j = i + gap; j < arr.length; j += gap) {
                    //获取当前元素,然后在本组内部向前比较并排序
                    int current = arr[j];
                    for (int k = j - gap; k >= i; k -= gap) {
                        if (arr[k] > current) {
                            //插入
                            arr[k + gap] = arr[k];
                            arr[k] = current;
                        }
                    }
                }
            }
    
            if (gap > 1) {
                sort(arr, gap);
            }
        }
    }
    

    输出:

    2
    3
    9
    10
    22
    34
    55
    67
    69
    89
    92
    99
    101
    102

    本文动图演示引自:https://www.cnblogs.com/onepixel/articles/7674659.html

    展开全文
  • Java希尔排序算法代码实现时间:2017-08-30来源:华清远见JAVA学院什么是Java希尔排序算法呢?希尔排序算法实际上是一种分组插入的排序算法,又被称为缩小增量排序。今天华清Java学院小编就来和大家分享下Java希尔...

    Java希尔排序算法代码实现

    时间:2017-08-30     来源:华清远见JAVA学院

    什么是Java希尔排序算法呢?

    希尔排序算法实际上是一种分组插入的排序算法,又被称为缩小增量排序。今天华清Java学院小编就来和大家分享下Java希尔排序算法代码实现。

    Java希尔排序算法是的基本思想是:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序;然后,取第二个增量d2

    对于插入排序而言,如果原数组是基本有序的,那排序效率就可大大提高。另外,对于数量较小的序列使用直接插入排序,会因需要移动的数据量少,其效率也会提高。因此,希尔排序具有较高的执行效率,其实现原理如下图。

    8e31c494102932c56e0c2cdb085c290f.png

    Java希尔排序算法实现原理图

    Java希尔排序算法实现示例代码如下:

    public static void shellSortSmallToBig(int[] data) {

    int j = 0;

    int temp = 0;

    for (int increment = data.length / 2; increment > 0; increment /= 2) {

    System.out.println("increment:" + increment);

    for (int i = increment; i < data.length; i++) {

    // System.out.println("i:" + i);

    temp = data[i];

    for (j = i - increment; j >= 0; j -= increment) {

    // System.out.println("j:" + j);

    // System.out.println("temp:" + temp);

    // System.out.println("data[" + j + "]:" + data[j]);

    if (temp < data[j]) {

    data[j + increment] = data[j];

    } else {

    break;

    }}

    data[j + increment] = temp;

    }

    for (int i = 0; i < data.length; i++)

    System.out.print(data[i] + " ");

    }}

    public static void main(String[] args) {

    int[] data = new int[] { 26, 53, 67, 48, 57, 13, 48, 32, 60, 50 };

    shellSortSmallToBig(data);

    System.out.println(Arrays.toString(data));

    }

    展开全文
  • 希尔排序算法的算法思想、动态演示、C++、python实现可以参考希尔排序算法详解 希尔排序是一种插入类排序。...java实现希尔排序算法 public static int[] ShellSort(int[] arr){ int n=arr.leng...

    希尔排序算法的算法思想、动态演示、C++、python实现可以参考希尔排序算法详解
    希尔排序是一种插入类排序。直接插入的加强版。
    算法思想:参见希尔排序算法详解
    算法的性能分析
    希尔排序算法
    希尔排序中相等数据可能会交换位置,所以希尔排序是不稳定的算法。

    java实现希尔排序算法
    	public static int[] ShellSort(int[] arr){
            int n=arr.length;
            int gap=n/2;
            while(gap>0){
                for(int j=gap;j<n;j++){
                	for(int i=j;i>=gap;i-=gap)
                	 if(arr[i]<arr[i-gap]){
                         int temp=arr[i];
                         arr[i]=arr[i-gap];
                         arr[i-gap]=temp;
                    }   
                }
                gap=gap/2;
    
            }
            return arr;
        }
    
    总结

    1.希尔排序又叫缩小增量排序。即增量前后进行比较。
    2.注意增量的大小。每次n/2。
    3.等到增量为1时就是直接插入排序。

    展开全文
  • 希尔排序算法Java实现

    2021-03-01 07:17:49
    希尔排序(Shell Sort)是插入排序的一种,它是针对直接插入排序算法的改进。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。希尔排序实质上是一种分组插入方法。它的基本思想是:对于n个待排序的数列,取一...

    希尔排序(Shell Sort)是插入排序的一种,它是针对直接插入排序算法的改进。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。

    希尔排序实质上是一种分组插入方法。它的基本思想是:对于n个待排序的数列,取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列,所有距离为gap的倍数的记录放在同一个组中;然后,对各组内的元素进行直接插入排序。 这一趟排序完成之后,每一个组的元素都是有序的。然后减小gap的值,并重复执行上述的分组和排序。重复这样的操作,当gap=1时,整个数列就是有序的。

    package com.neuedu.algorithm;

    import java.util.Arrays;

    public class ShellSort {

    //先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,

    //然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,

    //再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下(接近最好情况),

    publicstatic void Shell(int Array[],int n){

    int d=n/2; //设置起始增量

    while(d >= 1)

    { //增量为1时排序结束

    for(int k=0;k

    { //遍历所有的子序

    for(int i=k+d;i

    { //对每个子序进行插入排序

    int temp=Array[i]; //插入排序算法参见链接

    int j=i-d;

    while(j>=k && Array[j]>temp)

    {

    Array[j+d]=Array[j];

    j=j-d;

    }

    Array[j+d]=temp;

    }

    }

    d=d/2; //缩小增量

    }

    }

    public static void main(String []args){

    int []arr = {9,8,7,6,5,4,3,2,1};

    Shell(arr, arr.length);

    System.out.println(Arrays.toString(arr));

    }

    }

    展开全文
  • title: 希尔排序算法(基于Java实现) tags: 希尔排序算法 希尔排序算法的原理与代码实现: 一、希尔排序算法的原理 因为在简单插入排序中可能会存在这样的问题,例如,我们将数组arr=[2, 3, 4, 5, 6, 1]进行排序,...
  • 希尔排序是希尔(DonaldShell) 于1959年提出的一种排序算法希尔排序也是一种插入排序,它是简单插入排序经过改进之后的-一个更高效的版本,也称为缩小增量排序。 ➢ 希尔排序基本思想 希尔排序是把记录按下标的一定...
  • 希尔排序是特殊的插入排序算法, 按照百度百科的定义为: 希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非...
  • java 算法希尔排序一、思想希尔排序:使数组中任意间隔为h的元素都是有序的。在进行排序的时候,如果h很大,我们就能将元素移动到很远的地方,为实现更小的h有序创造方便。用这种方式,对任意以1结尾的h序列,我们...
  • Java实现希尔排序

    2021-03-16 13:18:42
    理论准备希尔排序(Shell Sort)是插入排序的一种,是针对直接插入排序算法的改进,是将整个无序列分割成若干小的子序列分别进行插入排序,希尔排序并不稳定。该方法又称缩小增量排序,因DL.Shell...
  • 1.插入排序存在问题数组 arr = {2,3,4,5,6,1} ,在需要插入的数 1(最小)时,过程为:{2,3,4,5,6,6}{2,3,4,5,5,6}{2,3,4,4,5,6}{2,3,3,4,5,6}{2,2,3,4,5,6}{1,2...2. 希尔排序介绍希尔排序是希尔(Donald Shell)于1959...
  • 希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。 ...
  • 一:希尔排序算法基本思想希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell...
  • 希尔排序是插入排序的一种,又称“缩小增量排序”,是插入排序算法的一种更高效的改进版本。 前面学习插入排序的时候,我们会发现一个很不友好的事儿,如果已排序的分组元素为{2,5,7,9,10},未排序的分组 元素为{1,8...
  • java实现希尔排序(思路与实现

    万次阅读 多人点赞 2018-06-06 18:05:38
    希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个...
  • 因为希尔排序的核心思想是插入排序,所以本篇将两篇排序一起记录本篇内容:插入排序希尔排序(一)插入排序算法思想:把n个待排序的元素看成一个有序表和一个无序表,开始时有序表中只有一个元素,无序表中有n-1个元素...
  • 希尔排序算法实现与解析 从直接插入排序的算法中我们可以明显看到,如果数据越有序,直接插入排序的效率也就会越高。 而希尔排序,就是基于这一点的一个插入排序算法。 希尔排序的基本思想是,先将数据按照一个间隔...
  • Java实现希尔排序图解

    2020-06-09 14:01:28
    目录简单插入排序存在的问题希尔排序法介绍希尔排序法基本思想排序思想图解代码实现 简单插入排序存在的问题 假如数组arr={2,3,4,5,6,1},这时需要插入的数为1,这样的过程是 {2,3,4,5,6,6} {2,3,4,5,5,6} {2...
  • 主要介绍了希尔排序算法与相关的Java代码实现,希尔排序的时间复杂度根据步长序列的不同而不同,需要的朋友可以参考下
  • 简单插入排序问题 我们看简单的插入排序可能存在的问题,数组 arr = { 2, 3, 4, 5, 6, 1 } 这时需要插入的数 1(最小),简单插入排序的过程如下 ...希尔排序是希尔(Donald Shell) 于 1959 年提出的一种排序算法
  • 主要介绍了Java如何实现八个常用的排序算法:插入排序、冒泡排序、选择排序、希尔排序 、快速排序、归并排序、堆排序和LST基数排序,需要的朋友可以参考下
  • java实现希尔排序

    2019-08-21 00:08:55
    希尔排序算法描述: 将一个数据序列分成若干组,每组由若干相隔一段距离(称为增量delta)的元素组成,在一个组内采用直接插入排序算法进行排序。 增量delta初值通常为数据序列长度的一半,以后每趟增量减半,最后...
  • Java实现十大排序算法

    千次阅读 多人点赞 2019-12-04 16:35:23
    今天我们来用Java实现一下经典的十大排序算法 具体代码与文件可访问我的GitHub地址获取 https://github.com/liuzuoping/Algorithms PS:欢迎star 1 冒泡排序 冒泡排序无疑是最为出名的排序算法之一,从序列的一端...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 20,493
精华内容 8,197
关键字:

java实现希尔排序算法

java 订阅