【不三不四的脑洞】一个梦所引发关于排序算法的思考

【不三不四的脑洞】一个梦所引发关于排序算法的思考

前一段时间，我做了一个梦

一个漆黑的深夜里，我正在躲避日本皇军和伪满军人的追捕，突然发现前方有一个很大的古刹，虽然有点阴森，但是随着追兵的步步逼近，我也别无选择，只能咬咬牙打算藏身在里面。

我翻墙便进了寺庙，在里头转啊转啊，突然发现天空出现了几只小蝙蝠（因为离得远所以看着小），而且有越来越多的趋势，逐渐漫天都是，而且越变越大（开始往下降、准备着陆）。

我躲在大柱子后面观察其中先着陆的几只，大的有将近一人高，而且乍看之下有些人形。

直觉告诉我，此地不宜久留，我尽量回避它们的眼神，不敢直视它们的眼睛（依稀记得 Discovery 之类的探索频道有说过，盯着动物看是一种挑衅行为），但是情急之下我还是得强装镇定的往前继续走，心中一边默念 “佛祖保佑！佛祖保佑！佛门净地，不能杀生，希望它们对人不感兴趣，不会吃人。。。”。

我往前走着走着，不知经过了多久，忽然发现前方有几个蝙蝠队伍，它们有序聚集在各自对应的小窗户前。我凑近仔细观察，发现原来是它们正在从中领取一种食物。

突然背后有什么东西拍了拍我的肩膀（着实吓了我一跳），我惊恐地回头一看，原来是位面容清秀的小沙弥，他微微一笑告诉我：“施主莫慌，看您是生面孔，想必是第一次来敝寺。您所见的这些巨蝙蝠是敝寺的守护，性格温顺，不轻易伤人，如若有邪物想进犯本寺，它们就会倾巢而出赶走邪物，那些追捕你的军队，已经被它们所吓跑，施主不必多虑。此外，它们所吃的东西叫 ‘尸净’，是它们的最爱。”

说着，他便拿出一块来，我凑近一看，那个食物看起来是一种小小的带有人形的果冻（胶状体），但是通体晶莹，有多种颜色。

说着这位小沙弥就邀请我进了他们的后厨。进屋一看，我被眼前的一切所 震惊 了。。。他们的炊具 —— 竟然是一个 马桶型 的大锅，里头烧着满满的一锅杂烩，各种各样的颜色，但是看不出是什么食材。

小沙弥继续介绍说，其实他们也不用往里头加任何食材，只要加 “水” 熬制七七四十九个小时就能形成晶莹剔透的胶状物质。“是什么神奇的水吗？” 我好奇地问道。小沙弥说：“是洗干净尸体的水”。。。（听到此处，我心中不自觉一阵翻江倒海。。。）

越怕什么越来什么，说话间，小沙弥便热情地用大勺盛了一碗给我，虽然心中万般不情愿，但是无奈盛情难却，我又脸皮薄不好意思拒绝，所以。。。正当我在考虑先吃哪一碗的时候突然灵机一动，岔开话题，询问小沙弥他们这样给蝙蝠发食物是否有遇到过什么效率问题。小沙弥说：“的确是有一个问题，虽然这些蝙蝠很有素质，能够依序排队领取食物，但是每只蝙蝠的食量却不一样，有多有少，要是能够对它们依据食量提前进行排序就好了！”

小沙弥还提醒了我有额外要求：

时间复杂度：nlogn空间复杂度：常量

听到这里，我突然醒了，但是本着对小沙弥负责的态度，我还是敏感地发觉这是一个 LeetCode 148 相关的排序问题 ！

所以

如何才能满足上述要求对蝙蝠进行排序？

首先，通过查阅相关资料，常见的几种排序算法的性能如下

从上表可知，堆排序在 数组 情况下、归并排序（自下而上）在 链表 情况下都满足以上条件。我这里着重介绍一下 归并排序（自下而上）

代码和详细注释如下

/// @note 代码原作者: Huahua/// 详细注释：ShaderJoy/// @note 一只蝙蝠结点struct ListNode{ int val; ///< 蝙蝠食量 ListNode *next; ///< 后一只蝙蝠 ListNode(int x): val(x), next(NULL){}};class Solution {public: ListNode* sortList(ListNode* head) { /// @note 完成状态，只剩 0 或者 1 只蝙蝠 if (!head || !head->next) return head; int len = 1; ListNode* cur = head; while (cur = cur->next) ++len; ///< 首先统计队列中有多少只蝙蝠 ///@note 工具结点 ListNode dummy(0); dummy.next = head; ///< 它的后面保存的是头蝙蝠 ListNode* l; ListNode* r; ListNode* tail; /// @note n 表示每个分组的蝙蝠个数 /// 每次迭代后 n 都会翻倍 /// 保证执行 log(len) 次 for (int n = 1; n < len; n <<= 1) { cur = dummy.next; ///< 当前处理的队头蝙蝠（已经部分排序的头） tail = &dummy; ///< 队尾 while (cur) { l = cur; r = split(l, n); ///< 这两行代码将当前列表分割两次，结果是 l 和 r 都是 n 个蝙蝠 cur = split(r, n); ///< 而此时 cur 指向了 l 和 r 的后面 auto merged = merge(l, r); ///< 将两个列表进行合并（并从小到大排序） tail->next = merged.first; ///< 合并且有序的 head 接到 tail 的后面 tail = merged.second; ///< 合并且有序的 tail 成为新的 tail } } return dummy.next; }private: /// @note 将列表分成两部分，前 n 个元素和其余元素。 /// 返回其余部分的头。 ListNode* split(ListNode* head, int n) { /// @note 往后走 n 步 while (--n && head) head = head->next; /// @note 把 rest 保存此时的 head 后方（如果 head 存在的话） ListNode* rest = head ? head->next : nullptr; /// @note 断开 head 后方 if (head) head->next = nullptr; return rest; } /// @note 合并两个列表，返回合并后列表的头和尾。 pair merge(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* tail = &dummy; while (l1 && l2) { /// @note 将小的放在 l1，大的放在 l2 （所以 while 循环中始终只要操作 l1 和 tail） if (l1->val > l2->val) swap(l1, l2); tail->next = l1; ///< 保存 l1 为 tail 的下一位 l1 = l1->next; ///< l1 后移一位（继续和 l2 比较） tail = tail->next; ///< tail 也后移一位 } tail->next = l1 ? l1 : l2; ///< 善后 l1, l2 while (tail->next) tail = tail->next; ///< 并让 tail 指向合并后队列的尾部 return {dummy.next, tail}; }};

程序运行结果如下（以 4 只蝙蝠为例）

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。