梳排序算法讲解

梦里梦外; 2022-05-11 07:18 214阅读 0赞

嗯，历史山这些算法的名字总是，嗯，不知道如何说，反正充满了想象力，不过也恰恰形象的说明了这个算法

梳排序，跟梳子一样，齿和齿中间有间隙，这个间隙是多少呢，是1.3，嗯，记住就好，为啥是1.3，数学功底比较强的人可以去看看哈，我们这就不做太多讨论，直接举例

有数组\[6, 4, 5, 1, 8, 7, 2, 3\]

我们先来算算间隙，上面的数组长度为8，8/1.3=6，则间隙为6

我们开始遍历数组

第一遍，取间隙6

取下标0和6的数，分别是6和2，6比2大，进行互换，\[2, 4, 5, 1, 8, 7, 6, 3\]

取下标1和7的数，分别是4和3，4比3大，进行互换，\[2, 3, 5, 1, 8, 7, 6, 4\]

第二遍，取间隙6/1.3=4

取下标0和4的数，分别是2和8，顺序正确，则不互换，\[2, 3, 5, 1, 8, 7, 6, 4\]

取下标1和5的数，分别是3和7，顺序正确，则不互换，\[2, 3, 5, 1, 8, 7, 6, 4\]

取下标2和6的数，分别是5和6，顺序正确，则不互换，\[2, 3, 5, 1, 8, 7, 6, 4\]

取下标3和7的数，分别是1和4，顺序正确，则不互换，\[2, 3, 5, 1, 8, 7, 6, 4\]

第三遍，取间隙4/1.3=3

取下标0和3的数，分别是2和1，2比1大，进行互换，\[1, 3, 5, 2, 8, 7, 6, 4\]

取下标1和4的数，分别是3和8，顺序正确，则不互换，\[1, 3, 5, 2, 8, 7, 6, 4\]

取下标2和5的数，分别是5和7，顺序正确，则不互换，\[1, 3, 5, 2, 8, 7, 6, 4\]

取下标3和6的数，分别是2和6，顺序正确，则不互换，\[1, 3, 5, 2, 8, 7, 6, 4\]

取下标4和7的数，分别是8和4，8比4大，进行互换，\[1, 3, 5, 2, 4, 7, 6, 8\]

第四遍，取间隙3/1.3=2

取下标0和2的数，分别是1和5，顺序正确，则不互换，\[1, 3, 5, 2, 4, 7, 6, 8\]

取下标1和3的数，分别是3和2，3比2大，进行互换，\[1, 2, 5, 3, 4, 7, 6, 8\]

取下标2和4的数，分别是5和4，5比4大，进行互换，\[1, 2, 4, 3, 5, 7, 6, 8\]

取下标3和5的数，分别是3和7，顺序正确，则不互换，\[1, 2, 4, 3, 5, 7, 6, 8\]

取下标4和6的数，分别是5和6，顺序正确，则不互换，\[1, 2, 4, 3, 5, 7, 6, 8\]

取下标5和7的数，分别是7和8，顺序正确，则不互换，\[1, 2, 4, 3, 5, 7, 6, 8\]

第五遍，取间歇2/1.3=1

取下标0和1的数，分别是1和3，顺序正确，则不互换，\[1, 3, 5, 2, 4, 7, 6, 8\]

取下标1和2的数，分别是2和5，顺序正确，则不互换，\[1, 2, 5, 3, 4, 7, 6, 8\]

取下标2和3的数，分别是4和3，4比3大，进行互换，\[1, 2, 3, 4, 5, 7, 6, 8\]

取下标3和4的数，分别是3和7，顺序正确，则不互换，\[1, 2, 3, 4, 5, 7, 6, 8\]

取下标4和5的数，分别是5和6，顺序正确，则不互换，\[1, 2, 3, 4, 5, 7, 6, 8\]

取下标5和6的数，分别是7和8，顺序正确，则不互换，\[1, 2, 3, 4, 5, 7, 6, 8\]

取下标6和7的数，分别是7和8，顺序正确，则不互换，\[1, 2, 3, 4, 5, 7, 6, 8\]

因为1/1.3<1了，所以没法弄了，排序结束，这个时候我们看到，数组其实已经排好了，太神奇了哈

代码如下【点击获取】

[java实现梳排序][java]

[python实现梳排序][python]

[go实现梳排序][go]

[java]: https://blog.csdn.net/stronglyh/article/details/82795450
[python]: https://blog.csdn.net/stronglyh/article/details/82795442
[go]: https://blog.csdn.net/stronglyh/article/details/82795470

发表评论取消回复

表情：

评论列表（有 0 条评论，214人围观）

还没有评论，来说两句吧...

相关阅读

相关梳排序Java实现

照算法笔记给的伪代码写了实现如下： public static int[] order(int[] array) { int n = array.l...

r囧r小猫/ 2024年04月18日 05:35/ 0 赞/ 72 阅读

相关梳排序

梳排序梳排序和希尔排序很类似。希尔排序是在直接插入排序的基础上做的优化，而梳排序是在冒泡排序的基础上做的优化，也就是将相距某个增量 d 的记录组成一个子序列，通

痛定思痛。/ 2022年05月25日 14:07/ 0 赞/ 188 阅读

相关快速排序算法讲解

看到名字，感觉很腻害，嗯，今天我们来讲解下这个比较腻害的算法思路如下：首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有

电玩女神/ 2022年05月15日 08:39/ 0 赞/ 205 阅读

相关选择排序算法讲解

选择排序，就是直接从待排序数组里选择一个最小(或最大)的数字,每次都拿一个最小数字出来，和剩下的数进行比较，再顺序放入新数组,直到全部拿完举个例子，有数组\[10, 1,

本是古典何须时尚/ 2022年05月14日 01:05/ 0 赞/ 164 阅读

相关 go实现梳排序算法

前面我详细讲解了[梳排序算法][Link 1]，现在我们用代码来实现下 package main import "fmt" //梳

待我称王封你为后i/ 2022年05月11日 07:26/ 0 赞/ 342 阅读

相关 java实现梳排序算法

前面我详细讲解了[梳排序算法][Link 1]，现在我们用代码来实现下 package ttt; public class CombSort {

浅浅的花香味﹌/ 2022年05月11日 07:26/ 0 赞/ 175 阅读

相关 python实现梳排序算法

前面我详细讲解了[梳排序算法][Link 1]，现在我们用python代码代码来实现下 !/usr/bin/python -- coding: utf-8

爱被打了一巴掌/ 2022年05月11日 07:26/ 0 赞/ 212 阅读

相关梳排序算法讲解

嗯，历史山这些算法的名字总是，嗯，不知道如何说，反正充满了想象力，不过也恰恰形象的说明了这个算法梳排序，跟梳子一样，齿和齿中间有间隙，这个间隙是多少呢，是1.3，嗯，记住就

梦里梦外;/ 2022年05月11日 07:18/ 0 赞/ 215 阅读

相关计数排序算法讲解

前面我讲解了一个[基数排序算法][Link 1]，这地方要说一下哈，同音不同字，不要弄混淆了今天我们讲的这个算法呢，这，这，这，又一个看名字就能看出来一点道道的，的确，计数

水深无声/ 2022年05月10日 04:56/ 0 赞/ 221 阅读

相关归并排序算法讲解

归并排序算法是一款十分高效的算法，因为用到了二叉树的特性，我们知道能使用二叉树特性的排序都比较高效，我们详细讲解一下比如有两个已经排好的数组（\[5,7\],\[2,6,1

怼烎@/ 2022年05月09日 00:22/ 0 赞/ 161 阅读