展开

关键词

排序算法 --- 希尔排序

一、排序思想 之前说到插入排序希尔排序就对其进行了一个优化,优化的思路是: 对待排序列进行分组,组数为gap = arr.length / 2; 对每一组进行插入排序,然后再进行分组,gap = gap / 2; 再对每一组进行插入排序,直到最后组数为1,再进行最后一次插入排序即可; ---- 欢迎大家关注我的公众号 javawebkf,目前正在慢慢地将简书文章搬到公众号,以后简书和公众号文章将同步更新 ,那么整个排序过程就完了。 二、代码实现 关于希尔的代码实现,网上很多花里胡哨的答案,什么交换法位移法之类的,其实不要想得那么复杂。 刚才说了,希尔排序的主要思想就是分组,对每一组分别进行插入排序,那代码就简单了,就是这分组里面将之前插入排序的代码拷过来稍微改改就行了。

13231

排序算法-希尔排序

上一篇讲解了简单插入排序算法,以及在其基础上优化的二分插入排序算法,但是每次插入需要按间隔为 1 移动有序区的元素,效率不高,下面我们来介绍一种新的插入排序算法-希尔排序算法简介 希尔排序(Shell Sort),也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。 然后算法再取越来越小的步长进行排序算法的最后一步就是普通的插入排序,但是到了这步,需排序的数据几乎是已排好的了(因为直接插入排序在元素基本有序的情况下,效率是很高的)。 算法描述 先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差d。 希尔排序会破坏元素间相互位置,因此希尔排序是不稳定的。

65840
  • 广告
    关闭

    老用户专属续费福利

    云服务器CVM、轻量应用服务器1.5折续费券等您来抽!

  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    算法-排序算法-希尔排序

    /** * 排序算法-希尔排序 * 冒泡排序算法、选择排序算法和插入排序算法,虽然思路比较直观,但是排序的效率比较低。 * 对于大量的数据需要排序时,往往需要寻求其他更为高效的排序算法。 Shell排序算法便是其中一种 * Shell排序算法严格来说基于插入排序的思想,其又称为希尔排序或者缩小增量排序,思路如下: * (1)将有n个元素的数组分成n/2个数字序列,第1个数据和第n/2 * (3)然后,再变为n/4个序列,再次排序。 * (4)不断重复上述过程,随着序列减少最后变为一个,也就完成了整个排序。 size; i++) { ints[i] = (int)(Math.random() * 100 ); } System.out.println("排序前的数组 :" + Arrays.toString(ints)); } System.out.println("排序后的数组:" + Arrays.toString(ints))

    13920

    排序算法-希尔排序

    排序算法-希尔排序 <?php /** * 希尔排序. * * 算法思路: * 给定一个初始步长,一般为序列长度的一半 * 按步长分组 * 每组进行插入排序 * 取当前步长的一半为下个步长,继续上面的算法 * 直到步长为1结束 * * @ param array $value 待排序数组 * @param array $increment 步长 初始数组长度向下取整 * * @return array */ function shell value = [], $increment) { // 步长小于1为止 if ($increment < 1) { return; } // 分组插入排序 $point = $a; // 已排序末尾初始位置 while (isset($value[$point + $increment])) { $next = $value

    33470

    排序算法希尔排序

    希尔排序法(缩小增量法) 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序的方法。 //shell排序 /* 基本思想:将序列分成几类,在类里将它分成几个小组,再让它在小组内进行排序,依次重复直至排序成功 1,找出间距gap(分类)最后间距分类必须为1, 第一重循环 2, 找出各组 , j,flag,gap=n; int tmmp; while(gap>1) { gap=gap/2;//缩小增量,每次减半 do//子序列应用冒泡排序 =0);//优化冒泡排序 } } main() { int i,a[10] = {-12,23,345,1,34,-45,34,3,2,5}; printf("原序列的元素排序为 for(i=0; i<10; i++) { printf("%d ",a[i]); } shellsort(a,10); printf("\n排序后的元素位置

    10510

    算法-希尔排序

    对关键字{10,20,8,25,35,6,18,30,5,15,28}序列进行希尔排序,取增量d =5时,排序结果为( ) A. {6,18,8,5,15,10,20,30,25,35,28} B. 】 希尔排序 希尔排序(Shell Sort)是插入排序的一种。 也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止 【代码实现】 方式一: package :"); for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } // 希尔排序 int d =

    19620

    希尔排序算法

    前言 当待插入元素是一个很小(当需求是从小到大排序时,从大到小排序时此处为很大)直接插入排序需要移动较多次数,性能会很差。希尔排序解决了这一问题。 基本思想 希尔排序的基本思想:把序列按下标的一定增量分组,对每组使用直接插入排序算法排序; 随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。 如果对直接插入排序不了解的朋友,可以看我的这篇文章: 详解直接插入排序算法 例子 给定数组arr为 [ 3 , 6 , 5 , 12 , 1 , 75 , 10 , -3, 0 ] 初始状态见下图: 内层循环就是插入排序的代码。 如果对直接插入排序不了解的朋友,可以看我的这篇文章: 详解直接插入排序算法 其他 希尔排序的时间复杂度有很多种说法,证明也比较复杂,本文不过多讨论。 关于稳定性: 在不同的插入排序过程中,相等的元素可能在各自的插入排序中发生移动,最后其前后相对位置会发生改变,所以希尔排序是不稳定的。

    31520

    希尔排序算法

    希尔排序算法是插入排序的一种变种。只是这种算法,增加了一些随机因素。插入排序是整个数据是一组进行排序希尔排序是把数据进行分组,进行排序,逐步减少组的数量,最后是一组,再进行一趟希尔排序希尔排序的关键点 本质上还是插入排序。 分组进行插入排序,按一定的间隔取数据组成一组,缩小间隔,组的数量步骤减少,最后形成一组进行插入排序。 举例说一下希尔排序, 以 6, 7, 4, 3, 8 为例 间隔 gap = 2 (数组长度除以2)得到, 6, 7, 4, 3, 8;分成三组(6,4)(7,3),(8) 2. 三组数据进行插入排序得到,4, 7, 6, 3, 8 3 . 缩小间隔 gap = gap / 2 = 1 , 这个时候就是一组数据(4, 7, 6, 3, 8)进行插入排序 以下是python代码实现的希尔排序 def shell_sort(elements):

    10930

    详解排序算法--希尔排序希尔排序算法思想步长序列

    希尔排序 希尔排序的由来是根据插入排序的。 读者若不了解插入排序,可以参考笔者的详解排序算法--插入排序和冒泡排序. 所以希尔排序一般不是交换相邻元素,而是跳跃一段距离交换。 算法思想 希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。 然后算法再取越来越小的步长进行排序算法的最后一步就是普通的插入排序,但是到了这步,需排序的数据几乎是已排好的了(此时插入排序较快)。 步长序列 步长的选择是希尔排序的重要部分。 算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序,最终算法以步长为1进行排序。当步长为1时,算法变为插入排序,这就保证了数据一定会被排序。 如果不是这样,那么算法在迭代过程中会打乱以前的顺序,那就不会以如此短的时间完成排序了。 ? Paste_Image.png 最优时间复杂度 O(n) 不稳定 希尔排序动态图 ?

    74030

    排序算法希尔排序

    希尔排序 希尔排序是优化后的插入排序,又名玄学排序,因为希尔排序是不稳定的。 希尔排序就是将一个数组分成间隔为h的子数组,并对这些子数组进行插入排序,通过不断地缩小h的值,从而满足插入排序适合的情形:数组基本有序,从而达到良好的性能。 难点 希尔排序的难点在于递增序列的选择,我使用的是《算法(第四版)》中推荐的递增序列,即1/2(3k-1),从N/3开始递减至1。 演示 ? ,发现希尔排序比插入排序和选择排序要快很多,尤其是数组越大的时候。 希尔排序最坏运行时间为O(n2),最好运行时间为O(n),平均运行时间为O(n1.3)。有经验的程序员有时会用到希尔排序,因为对于中等大小的数组,它的运行时间是可以被接受的,并且不占用额外的空间。

    17210

    排序算法(六):希尔排序

    希尔排序是对插入排序的一种改进,也叫递减增量排序算法过程中通过对增量值的递减调整,形成每一个增量值对应的一个或多个待排序分组,分别对分组执行插入排序,最后调整增量值为一,对最后的分组排序后即完成排序过程 算法过程 希尔排序算法中有一个关键概念:增量(increment),或者称之为步长或间隔(gap)更容易理解,它的作用是将序列中间隔为增量值大小的元素,提出出来作为一个分组。例如间隔大小为 ? 算法步骤: 根据增量 ? 值大小,将序列拆分为 ? 个分组 对每个分组执行插入排序算法,并对 ? 值按指定规则调整大小 重复步骤 1, 2,直到 ? 第二层循环是增量值对应的分组个数,第三和第四层循环结构基本与插入排序完全相同,作用就是对每个分组执行插入排序操作。 算法分析 希尔排序是一种不稳定排序算法排序过程中,存在两个元素跨多个位置的替换。 希尔排序属于原地排序算法,不需要申请额外的存储空间。它是在插入排序的基础上进行了改进,实际就是除了最后的插入排序外,对多个子分组也执行了排序

    97610

    浅析希尔排序算法

    希尔排序(Shell Sort)是插入排序的一种,它是针对直接插入排序算法的改进。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。 一、算法描述 希尔排序的思想是采用插入排序的方法,先让数组中任意间隔为 gap 的元素有序,刚开始 gap 的大小可以是 gap = n / 2,接着让 gap = (n / 2) / 2,让 h 一直缩小 时间复杂度:希尔排序的时间复杂度与增量(即,步长 gap )的选取有关。 例如,当增量为 1 时,希尔排序退化成了直接插入排序,此时的时间复杂度为 O(N²),而Hibbard增量的希尔排序的时间复杂度为 O(N3/2)。 五、适用场景 希尔排序是对直接插入排序的一种优化,可以用于大型的数组,希尔排序比插入排序和选择排序要快的多,并且数组越大,优势越大。

    15710

    希尔排序算法思想

    希尔排序算法思想 把记录按下标的一定增量分组,对每组使用 直接插入排序算法 排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。 希尔排序算法过程: 先取一个正整数gap ---- 例如数组a[49, 38, 65, 97, 26, 13, 27, 49, 55, 4] 第1次 步长 gap = 10 / 2 = 5 分成了五组( ---- 希尔排序的时间复杂度与增量序列的选取有关,例如希尔增量时间复杂度为O(n²),而Hibbard增量的希尔排序的时间复杂度为O(n^(3/2)),希尔排序时间复杂度的下界是n*log2n,希尔排序时间复杂度 希尔排序不是稳定排序算法算法实现 希尔排序算法伪代码 //希尔排序 input: an array a of length n with array elements numbered 0 to n − 1 gap ← round

    35430

    算法渣-排序-希尔

    没有一身好内功,招式再多都是空;算法绝对是防身必备,面试时更是不可或缺;跟着算法渣一起从零学算法 定义 希尔排序希尔(Donald Shell)于1959年提出的一种排序算法希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破O(n2)的第一批算法之一 算法 直接插入排序很循规蹈矩,不管数组分布是怎么样的,依然一步一步的对元素进行比较 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止 初始时,有一个大小为 10 的无序序列 在第一趟排序中,我们不妨设 gap1 = N / 2 = 5,即相隔距离为 5 的元素组成一组,可以分为 5 组 接下来,按照直接插入排序的方法对每个组进行排序 在第二趟排序中,我们把上次的 gap j=j-gap; } array[j+gap] = tmp; } } } 复杂度 希尔排序的时间复杂度与增量

    13930

    算法希尔排序学习笔记

    【参考资料】 《算法(第4版)》         — — Robert Sedgewick, Kevin Wayne 在本篇笔记里,我从简单的插入排序,到希尔排序,中间的一系列算法,看起来就像是插入排序的 这些点分别是: 直接插入排序(插入排序1.0版本) 基于插入排序的简单优化(插入排序1.1和1.2版本) 折半插入排序(插入排序2.0版本) 希尔排序(插入排序3.0版本) 直接插入排序(插入排序1.0 所以根据插排优于处理小型,部分有序数组的特性, 人们在插入排序的基础上设计出一种能够较好地处理中等规模的排序算法希尔排序 实现的过程 希尔排序又叫做步长递减插入排序或增量递减插入排序 (下面的h就是步长 第三轮分组排序,  h=1, 所以就是对整个数组进行直接插入排序希尔排序分析 人们设计希尔排序的思路可以简单描述为: “对症下药”, 因为插入排序擅长处理长度较短的, 部分有序(或有序)的数组, 那么就按这两点着手好了 (h=1时候对整个数组直接插排) 为何希尔排序后一定有序?

    43180

    Java常见排序算法详解——希尔排序

    概念: 希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。 然后算法再取越来越小的步长进行排序算法的最后一步就是普通的插入排序,但是到了这步,需排序的数据几乎是已排好的了(此时插入排序较快)。 希尔排序是基于插入排序的以下两点性质而提出改进方法的: 插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率 但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位 原理 array[j + number] = temp; } number = number / 2; } } 算法系列 : 冒泡排序 选择排序 直接插入排序 二分插入排序 希尔排序排序 完整代码: Java和Kotlin代码我均放在了GitHub上,欢迎Star!

    23700

    5-希尔排序算法

    思想: 增量排序,先部分有序,然后整体有序。 与插入排序的思想是一致的。 不稳定的排序算法 #include <stdio.h> void show(int *a, int n) { int i = 0; for (i = 0; i < n; i++)

    8540

    排序算法希尔排序-Java版

    希尔排序 1.1 希尔排序的基本介绍 1.2 希尔排序思想 1.3 希尔排序的时间复杂度和空间复杂度等 2. 代码演示 1. 希尔排序 1.1 希尔排序的基本介绍 希尔排序是加强版的插入排序,相对与普通的插入排序做了优化,比普通的插入排序多了一个步长的概念 1.2 希尔排序思想 就是把数据下标按照一定的步长进行分组,然后每组分别用普通插入排序进行排序 ,知道步长减至为 1 时,算法终止。 1.3 希尔排序的时间复杂度和空间复杂度等 算法名称 平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性 希尔排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定 2. %d arr:%s", j, insertIndex, Arrays.toString(arr)); System.out.println(); } } } } 代码基本与普通插入排序一致

    33410

    相关产品

    • 智能推荐平台

      智能推荐平台

      集生态、技术、场景于一体,采用业界领先的AI学习技术和智能推荐算法,基于腾讯多年在超大型场景中积累的最佳实践方法论,助力客户业务实现增长的企业级应用产品。

    相关资讯

    热门标签

    活动推荐

    扫码关注腾讯云开发者

    领取腾讯云代金券