偶看新闻gemini王者荣耀:9.6 希尔排序
来源：百度文库 编辑：偶看新闻 时间：2024/04/28 23:46:14
9.6 希尔排序
给大家出一道智力题。请问“VII”是什么？
嗯，很好，它是罗马数字的7。现在我们要给它加上一笔，让它变成8（VIII），应该是非常简单，只需要在右侧加一竖线即可。
现在我请大家试着对罗马数字9，也就是“IX”增加一笔，把它变成6，应该怎么做？
（几分钟后）
我已经听不少声音说，“这怎么可能！”
可为什么一定要用常规方法呢？我这里有3种另类的方法可以实现它。
方法一：观察发现“X”其实可以看作是一个正放一个倒置两个“V”。因此我们，给“IX”中间加一条水平线，上下颠倒，然后遮住下面部分，也就是说，我们所谓的加上一笔就是遮住一部分，于是就得到“VI”，如图9‐6‐1所示。
图9-6-1方法二：在“IX”前面加一个“S”，此时构成一个英文单词“SIX”，这就等于得到一个6了。哈哈，我听到下面一片哗然，我刚有没有说一定要是“VI”呀，我只说把它变成6而已，至于是罗马数字还是英文单词，我可没有限制。显然，你们的思维受到了我前面举例的“VII”转变为“VIII”的影响，如图9‐6‐2所示。
图9-6-2方法三：在“IX”后面加一个“6”，得到“1X6”，其结果当然是数字6了。大家笑了，因为这个想法实在是过分，把字母“I”当成了数字1，字母“X”看成了乘号。可谁又规定说这是不可以的呢？只要没违反规则，得到6即可，如图9‐6‐3所示。
图9-6-3智力题的答案介绍完了1。大家会发现，看似解决不了的问题，还真不一定就没有办法，也许只是暂时没想到罢了。
我们都能理解，优秀排序算法的首要条件就是速度2。于是人们想了许许多多的办法，目的就是为了提高排序的速度。而在很长的时间里，众人发现尽管各种排序算法花样繁多（比如前面我们提到的三种不同的排序算法），但时间复杂度都是O(n2)，似乎没法超越了3。此时，计算机学术界充斥着“排序算法不可能突破O(n2)”的声音。就像刚才大家做智力题的感觉一样，“不可能”成了主流。
终于有一天，当一位科学家发布超越了O(n2)新排序算法后，紧接着就出现了好几种可以超越O(n2)的排序算法，并把内排序算法的时间复杂度提升到了O(nlogn)。“不可能超越O(n2)”彻底成为了历史。
从这里也告诉我们，做任何事，你解决不了时，想一想“Nothing is impossible!”，虽然有点唯心，但这样的思维方式会让你更加深入地思考解决方案，而不是匆忙的放弃。
注：1本智力题摘自《在脑袋一侧猛敲一下》。
注：2还有其他要求，速度是第一位。
注意：3这里排序是指内排序。