搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 大数据记事本 > 图解希尔排序的交换法和移位法

图解希尔排序的交换法和移位法

大数据记事本 2020-08-02
       在《 一篇中,我们分析了插入排序,插入排序的过程是将无序区间中的元素依次插入到有序区间中。但是,以升序排列为例,如果数值较小的元素都靠后,那么在查找插入位置时,就需要移动多个元素,从而增加排序花费的时间。
      希尔排序是在插入排序的基础上优化而来的,它把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
   希尔排序的实现分为交换法和移位法两种,相对交换法,移位法的效率更高,下面我们来分析这两种方法。
一、交换法
    交换法是将每个组中的所有元素两两比较,不满足顺序即交换。假设有下面一组元素,采用交换法的流程如下:

①先对原始数组进行分组,增量=数组长度/2=10/2=5,下面颜色相同的元素表示同一组:

图解希尔排序的交换法和移位法

②从每组的第二个元素开始,依次和前面的所有元素比较大小, 和下标为0的元素同组的第二个元素的下标为0+增量(这里用gap表示),所以从gap开始:

图解希尔排序的交换法和移位法

③这里第一组的元素分别为8和3,不满足顺序,进行交换,然后gap后移,直到遍历完所有元素,此时每个组内的元素有序:

图解希尔排序的交换法和移位法

④缩小增量为原来的一半,5/2=2,重新进行分组:

图解希尔排序的交换法和移位法

⑤重复②③步骤,使每个组内的元素有序:

⑥再次缩小增量为原来的一半,2/2=1,重新分组,此时所有的元素都在一个组内

图解希尔排序的交换法和移位法

⑦从第二个元素开始依次和前面的元素比较,不满足顺序则交换,当所有元素交换完后,即排序完成,如下图:


代码实现:

public static int[] transShellSort(int[] arr) { int tmp = 0; int len = arr.length; //增量从数组长度/2开始,之后每次都/2,只要得到的增量大于0,就一直循环 for (int gap = len / 2; gap > 0; gap /= 2) { //从每组的第二个元素开始,依次和前面的所有元素比较大小, // 和下标为0的元素同组的第二个元素的下标为0+gap,所以从gap开始 for (int i = gap; i < arr.length; i++) { //j从i的前一个元素开始,直到遍历i前面的所有同组元素 for (int j = i - gap; j >= 0; j -= gap) { //这里虽然定义j=i-gap,但这只是初始j的值,当j-=gap后这个等式便不再成立, // 所以交换时不能直接将arr[j]和arr[i]的值交换 if (arr[j] > arr[j + gap]) { tmp = arr[j]; arr[j] = arr[j + gap]; arr[j + gap] = tmp; } } } } return arr;    }


二、移位法

   和交换法相比,移位法是对每个组直接进行插入排序。还是采用上面那组元素:

   我们以增量缩小为2时举例,此时所有元素分为两组,分别为[3,1,0,9,7] 和 [5,6,8,4,2]

    分别对两组元素直接进行插入排序,具体流程可以看《》中关于插入排序的讲解。

    同样,当所有的元素分到一个组,即增量为1时,进行排序后的结果就是最终的排序结果。

代码实现:

public static int[] moveShellSort(int[] arr) { int tmp = 0; int len = arr.length; for (int gap = len / 2; gap > 0; gap /= 2) { //从第gap个元素开始,逐个对其所在的组进行直接插入排序 for (int i = gap; i < len; i++) { int j = i; //这里的tmp就相当于插入排序中的insertVal,而j-gap就相当于insertIndex tmp = arr[j]; //gap所在的组,前面的数如果大于待插入的数,那么表示没有找到插入位置, // 其中arr[j]和arr[j-gap]为同组相邻的两个数 if (arr[j] < arr[j - gap]) { while (j - gap >= 0 && arr[j - gap] > tmp) { arr[j] = arr[j - gap]; //下标前移量为步长 j -= gap; } //当跳出while循环时,表示找到了插入位置 //当j-gap小于0时,tmp的位置下标就是j-gap+gap=j arr[j] = tmp; } } } return arr; }


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《图解希尔排序的交换法和移位法》的版权归原作者「大数据记事本」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注大数据记事本微信公众号

大数据记事本微信公众号:gh_e6d14f46e842

大数据记事本

手机扫描上方二维码即可关注大数据记事本微信公众号

大数据记事本最新文章

精品公众号随机推荐