【白话排序算法】希尔/谢尔排序法

傷城~ 2022-12-24 11:59 149阅读 0赞

谢尔排序法（Shell’s Sort）又称缩小增量排序法。他在1959年由谢尔（D.L.Shell）提出的。当时主流的排序算法时间复杂度都是 O ( n 2 ) O(n^2) O(n2)。谢尔排序是有望突破这个复杂度的一批算法之一。题外话，对比现在如此多O(nlogn)时间复杂度的排序算法，可见当时人们对排序算法的认知匮乏。你如果能穿越回60年前，绝对是一个了不起的人…

谢尔排序理解起来还是有些困难的。不过我可以试图解释下面这样一个思想，你应该能感觉到谢尔排序是可以降低时间复杂度的。

以下内容需要您对冒泡排序有一定的理解，可以看看我之前写的关于[冒泡排序][Link 1]的文章。

在冒泡排序中，核心是相邻两个元素交替位置，在这个过程中，其实大量的没有必要的交换，即交换之后会再被交换。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ1OTg2Ng_size_16_color_FFFFFF_t_70]  
观察一下`9`这个数，为了让他能够到正确的位置，所有**其他元素**都不得不进行位置的交替。而这些**其他元素**的位置交替仅仅是为了让`9`能够冒泡上去。

那么有没有可能在交替的过程中，让**其他元素哪怕至少能够离其最终的位置近一些**。因为我们知道，冒泡排序有一个特点：

若待排序的序列是倒序的，那么冒泡排序时间复杂度是 O ( n 2 ) O(n^2) O(n2)，若待排序的序列本身就是有序的，时间复杂度仅仅为O(n)。即，**若待排序的序列基本有序，时间复杂度将会大幅降低**。

谢尔排序正是利用了这样一个特点，当位置交替的时候，尽可能让交替变的有意义，即那些大的元素尽量往后排，而小的元素尽量往前排，让一趟交替后，让序列尽可能的有序一些，来达到最终降低时间复杂度的目的。

这样一个思想是可行的，你能明白么？下面来说一下如何实现。

为了能够让大的元素往后排，小的元素往前排，谢尔排序会以子序列的方式**跳跃的交替元素的位置**，这里也就是冒泡排序，进而让序列尽可能有序。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ1OTg2Ng_size_16_color_FFFFFF_t_70 1]  
观察下上图，可以把相当颜色的元素集合看成一个子序列，并对子序列进行冒泡排序（或其他的排序方式），而一趟结束的结果是不是已经实现了某种程序上接近有序了？谢尔排序之后通过不断缩小**间隔元素**的大小，当间隔为1去进行排序的时候，已经相当于完整的冒泡排序，但此时序列已经基本有序。从而实现了尽可能的降低时间复杂度的目的，很巧妙吧。下面我来用JavaScript语言来实现下：

关于算法中的gap取值，实际上并没有确定的规则，每次取序列长度的一半似乎是一种比较常用的方法。

谢尔排序需要去仔细的思考其思想。相对于插入，选择，冒泡，包含后边说的快排，都难理解一些。希望读者能静下心来，慢慢想想，就不难理解了。

我来总结一下我个人的思考：谢尔排序就是通过排序子序列的方式，让原有的序列**不断的接近有序**，再利用基本有序的序列排序时间复杂度低的特性，来最终通过一次完整的排序保证结果有序。

另外值得注意的是，谢尔排序的时间复杂度是介于 O ( n 2 ) O(n^2) O(n2)与O(nlogn)的。

谢尔排序的由于也涉及到了跨元素间的交换，所以是一种不稳定的排序方式。

[Link 1]: https://blog.csdn.net/weixin_43459866/article/details/110246729
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ1OTg2Ng_size_16_color_FFFFFF_t_70]: /images/20221120/d286a89f91ac4095b3e903d8c0a6b9d7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ1OTg2Ng_size_16_color_FFFFFF_t_70 1]: /images/20221120/57e45275fb39402db4f9ad6c8b2de3c6.png