【算法】希尔排序算法的解说和代码实践

计算机软件开发 · 2024-9-18 06:25:17

思绪

希尔排序，与其他排序差异的是，别的排序都能通过名字关联上，而希尔排序的名字，怎么看也不太像中文。
着实希尔排序就是插入排序的进化版，它会先声明一个间隙参数，然后按照间隙参数，把数组分成多少各子数组，对子数组举行插入排序。随着间隙越缩越小，整个数组的次序也就慢慢排好了。
看起来不太轻易明白，下面就拆开说一下步调：

盘算出一个间隙值；
按照间隙值把数组分成多少个子数组；
对子数组举行插入排序；
将间隙缩小，重新分组并插入排序；
直至整个数组排序完成。

解说

有数组如下：

如今要对它举行希尔排序。起首盘算出一个间隙值gap，我们用数组长度除以2，盘算出第一个gap：8 / 2 = 4；
那么隔断为4（比如下标为0的元素，加4，即下标为4的元素，两个元素看做一个子数组）的元素即为一个子数组，我们用差异颜色将子数组标记出来：

然后对子数组举行插入排序，插入排序前面的文章讲过了，这里就直接举行排序了：

然后将gap值自除2，盘算出下一个gap为：4 / 2 = 2，并将数组重新拆分子数组：

这次就分成了两个子数组，继续对这两个子数组举行排序：

次序越来越显着了。gap再次自除2，盘算出末了一个gap为：2 / 2 = 1，那么这次拆分出来的数组着实就是一个完备的数组了：

再次对数组举行排序：

整个数组的次序就拍好啦，这就是希尔排序。实现

【算法】希尔排序算法的解说和代码实践

所属分类: 问答交流

新帖推荐: 30日

推荐作品