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

目录
  • 希尔排序
  • 算法思想
  • 图解
  • 代码实现（Java）

希尔排序

希尔排序时插入排序的一种，也称缩小增量排序，是直接插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

算法思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序，随着增量逐渐减少，每组包含的数越来越多当增量减至1时，整个序列恰好被分成一组，算法完成。

我们以增序排序为例，希尔排序基本步骤：选择初始增量gap=length/2，缩小增量继续以gap=gap/2的方式进行，直到增量gap=1为止，增量的每次变化都会将原始序列划分为若干组，分别对每一组进行插入排序，每一次通过增量划分组进行插入排序宏观上小的数移到了前面，大的数移到了后面，最后增量gap=1进行插入排序后就是最终的有序序列。下面以图解的方式详细介绍希尔排序算法的整个流程。

图解

代码实现（Java）

public class ShellSort {
    public static void main(String[] args){
        int[] array = {86,11,54,34,53,12,45,81,19,65};
        int gap = array.length;
        while (true) {
            gap /= 2;   //增量每次减半
            for (int i = 0; i < gap; i++) {
                for (int j = i + gap; j < array.length; j += gap) {//这个循环里其实就是一个插入排序
                    int k = j - gap;
                    while (k >= 0 && array[k] > array[k+gap]) {
                        int temp = array[k];
                        array[k] = array[k+gap];
                        array[k + gap] = temp;
                        k -= gap;
                    }
                }
            }
            if (gap == 1)
                break;
        }
        System.out.println("排序结果：");
        for(int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
    }
}
//排序前：{86,11,54,34,53,12,45,81,19,65}
//排序后：{11,12,19,34,45,53,54,65,81,86}

到此这篇关于图解Java经典算法希尔排序的原理与实现的文章就介绍到这了,更多相关Java希尔排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • java数据结构之希尔排序

    希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本.希尔排序是非稳定排序算法. 希尔排序是基于插入排序的以下两点性质而提出改进方法的: 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率:         但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位. 实现: 先取一个正整数d1 < n, 把所有相隔d1的记录放一组,每个组内进行直接插入排序:然后d2 < d1,重复上述分组和排序操作:直至di = 1,即所有记录放进一个组中排序为止. 简

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

    图解排序算法之希尔排序Java实现

    一.基本思想 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序:随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止. 简单插入排序很循规蹈矩,不管数组分布是怎么样的,依然一步一步的对元素进行比较,移动,插入,比如[5,4,3,2,1,0]这种倒序序列,数组末端的0要回到首位置很是费劲,比较和移动元素均需n-1次.而希尔排序在数组中采用跳跃式分组的策略,通过某个增量将数组元素划分为若干组,然后分组进行插入排序,随后逐步缩小增量,继续按组

  • java数据结构与算法之希尔排序详解

    本文实例讲述了java数据结构与算法之希尔排序.分享给大家供大家参考,具体如下: 这里要介绍的是希尔排序(缩小增量排序法). 希尔排序:通过比较相距一定间隔的元素来工作:各趟比较所用的距离(增量)随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止.是插入排序的一种,是针对直接插入排序算法的改进. 算法思想:先将要排序的序列按某个增量d分成若干个子序列,对每个子序列中全部元素分别进行直接插入排序,然后再用一个较小的增量对它进行分组,在每组中再进行排序.当增量减到1时,整个要排序的数被分成一

  • Java 十大排序算法之希尔排序刨析

    Java 十大排序算法之希尔排序刨析

    目录 希尔排序原理 希尔排序的API设计 希尔排序的代码实现 希尔排序是插入排序的一种,又称"缩小增量排序",是插入排序算法的一种更高效的改进版本. 希尔排序原理 1.选定一个增长量h,按照增长量h作为数据分组的依据,对数据进行分组. 2.对分好组的每一组数据完成插入排序. 3.减小增长量,最小减为1,重复第二步操作. 希尔排序的API设计 类名 Shell 构造方法 Shell():创建Shell对象 成员方法 1.public static void sort(Comparable

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

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

    目录 基本思想 代码实现 总结 希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法.希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破O(n2)的第一批算法之一.本文会以图解的方式详细介绍希尔排序的基本思想及其代码实现. 基本思想 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序:随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止. 简单插入排序很循规蹈

  • Java 插入排序之希尔排序的实例

    Java 插入排序之希尔排序的实例 Java代码 /*希尔排序(Shell Sort)是插入排序的一种.其基本思想是:先取定一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1 * 个组,所有距离为d1的倍数的记录放在同一个组中,在各个组中进行插入排序:然后,取第二个增量d2<d1,重复上述的分组和排序, * 直至所取的增量dt=1(dt<dt-1<...<d2<d1),即所有记录放在同一组中进行直接插入排序为止. * new int[]{8,5,1,7,9,4,6}

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

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

  • JAVA十大排序算法之希尔排序详解

    JAVA十大排序算法之希尔排序详解

    目录 希尔排序 代码实现 时间复杂度 算法稳定性 总结 希尔排序 一种基于插入排序的快速的排序算法.简单插入排序对于大规模乱序数组很慢,因为元素只能一点一点地从数组的一端移动到另一端.例如,如果主键最小的元素正好在数组的尽头,要将它挪到正确的位置就需要n-1次移动. 希尔排序为了加快速度简单地改进了插入排序,也称为缩小增量排序. 希尔排序是把待排序数组按一定的数量分组,对每组使用直接插入排序算法排序:然后缩小数量继续分组排序,随着数量逐渐减少,每组包含的元素越来越多,当数量减至 1 时,整个数组

  • java 数据结构基本算法希尔排序

    C语言数据结构基本算法希尔排序 前言: 基本思想:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差d.对每组中全部元素进行直接插入排序, 然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序.当增量减到1时,进行直接插入排序后,排序完成. 实现代码: public class ShellSort { /** * 原理:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的 * 下标相差d.对每组

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

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

  • 图解Java经典算法冒泡选择插入希尔排序的原理与实现

    图解Java经典算法冒泡选择插入希尔排序的原理与实现

    目录 一.冒泡排序 1.基本介绍 2.代码实现 二. 选择排序 1.基本介绍 2.代码实现 三.插入排序 1.基本介绍 2.代码实现 四.希尔排序 1.基本介绍 2.代码实现(交换排序) 3.代码实现(移位排序) 一.冒泡排序 1.基本介绍 冒泡排序是重复地走访要排序的元素,依次比较两个相邻的元素,如果它们的顺序与自己规定的不符合,则把两个元素的位置交换.走访元素重复地进行,直到没有相邻元素需要交换为止,完成整个排序过程. 算法原理 1.比较相邻元素,如果前一个元素大于后一个元素,则交换. 2.

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

    图解Java经典算法插入排序的原理与实现

    目录 一.算法介绍 二.算法思想 三.算法原理 四.动图演示 五.代码实现 六.算法分析 6.1 时间复杂度 6.2 空间复杂度 一.算法介绍 插入排序,也称为直接插入排序.插入排序是简单排序中效率最好的一种,它也是学习其他高级排序的基础,比如希尔排序/快速排序,所以非常重要,而它相对于选择排序的优点就在于比较次数几乎是少了一半. 二.算法思想 每次将待排序的元素插入到已排序的序列中,直至全部插入完成. 三.算法原理 把所有元素分为两个序列,将第一待排序序列第一个元素看做一个有序序列,把第二个元

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

    图解Java经典算法快速排序的原理与实现

    目录 快速排序 算法原理 图解 Java代码实现 算法分析 快速排序 通过一趟排序将待排元素分成独立的两部分,其中一部分为比基准数小的元素,另一部分则是比基准数大的元素.然后对这两部分元素再按照前面的算法进行排序,直到每一部分的元素都只剩下一个. 本质上来看,快速排序应该算是在冒泡排序基础上的递归分治法. 算法原理 从数列中挑出一个元素作为基准点 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面 然后基准值左右两边,重复上述步骤 通过递归把基准值元素左右两侧的

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

    图解Java经典算法归并排序的原理与实现

    目录 归并排序 算法原理 动图演示 代码实现 复杂度 归并排序 归并排序主要分成两部分实现,分.合两部分,分是把数组分成两半,再递归的对子数组进行 分 操作,直到分成一个个单独的数.合是把两个数组合并为有序数组,在对有序数组进行合并,直到全部子数组合并为一个完整的数组. 算法原理 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 设定两个指针,最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置 重复步骤c直

  • Java经典设计模式之策略模式原理与用法详解

    Java经典设计模式之策略模式原理与用法详解

    本文实例讲述了Java经典设计模式之策略模式.分享给大家供大家参考,具体如下: 策略模式指:策略模式指将程序中可变部分抽象分离成一系列的算法,并将每一个算法封装起来,而且使它们还可以相互替换.策略模式让算法独立于使用它的客户而独立变化. 策略模式一般由下面三部分组成: 1. 抽象策略角色: 策略类,通常由一个接口或者抽象类实现. 2. 具体策略角色:包装了相关的算法和行为. 3. 环境角色:持有某一个策略类的引用,客户端调用. 策略模式设计原则: 1. 把程序中需要变化的部分抽离出来,独立于不变

  • Java经典算法汇总之选择排序（SelectionSort）

    Java经典算法汇总之选择排序（SelectionSort）

    a)原理:每一趟从待排序的记录中选出最小的元素,顺序放在已排好序的序列最后,直到全部记录排序完毕.也就是:每一趟在n-i+1(i=1,2,-n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录.基于此思想的算法主要有简单选择排序.树型选择排序和堆排序.(这里只介绍常用的简单选择排序) b)简单选择排序的基本思想:给定数组:int[]arr={里面n个数据}:第1趟排序,在待排序数据arr[1]~arr[n]中选出最小的数据,将它与arrr[1]交换:第2趟,在待排序数据arr[2]~ar

随机推荐