非常难的算法：希尔排序算法图及代码展示

希尔排序

希尔排序，也称为降序增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是一种不稳定的排序算法。

希尔排序基于插入排序的以下两个性质提出了一种改进方法：

• 插入排序在处理已经差不多排序的数据时非常高效，这意味着它可以达到线性排序的效率；
• 但是插入排序通常效率较低，因为插入排序一次只能移动一位数据；

希尔排序的基本思想是：首先，将整个待排序记录序列划分为若干子序列。直接插入排序是单独进行的，当整个序列中的记录“大部分OK”时，按顺序对所有记录进行直接插入排序。

算法步骤

1. 选择增量序列t1,t2,...,tk,其中ti > tj,tk = 1;
2. 按增量序列数 k 对序列进行 k 次排序；
3. 在每次排序过程中，将待排序的列根据对应的增量ti分成若干个长度为m的子序列，对每个子表进行直接插入排序。只有当缩放因子为1时，才将整个序列处理为表格，表格的长度就是整个序列的长度。

来源：github.com/hustcc/JS-S…

算法演示

动画排序过程讲解

1. 先选择增量间距=10/2，继续用间距=间隙/2的方法减少增量
2. 初始增量为gap = 10/2 = 5，整个场分为5组
3. 根据颜色分为[8, 3], [9, 5], [ 1, 4], [ 7 , 6], [2, 0]
4. 对这五个不同的组使用上一节中提到的插入排序。结果可以发现，这五组中相对较小的元素已经向前移动了
5. 减少了增量间隙=5/2=2，整个场被分成了2组
6. 【3,1 , 0 , 9 , 7 ], 【 5 , 6 , 8 , 4 , 2 】
7. 为此，两个单独的组使用上一节中提到的插入排序
8. 目前整个矩阵的顺序为​​非常明显
9. 然后减少增量间隙=2/2=1，整个矩阵分为1组
10. 【0, 2 , 1 , 4 , 3 , 5 , 7 , 6 , 9 , 0】
11. 目前只需要对上述矩阵做简单的微调就可以完成整个矩阵，不需要大量的移动操作。分类

代码实现

为了让读者更好地理解使用熟悉的编程语言的动画，作者将贴出几种编程语言的参考代码，全部来自网络。

C++ 代码实现

Java 代码实现

Python 代码实现

JavaScript 代码实现

如果您是 iOS 开发人员，您可以在 GitHub 上获得更直观的调试：github.com/MisterBooo/…实现源码。

作者：小吴哥
链接：https://juejin.im/post/5bf9f2285188256b0f5832a0
来源：掘金
版权归作者所有。商业转载请联系作者获得许可。非商业转载请注明来源。