排序算法的重大变革——一种O(n)的比较排序

· · 休闲·娱乐

似乎有人真的被文章里面描述的内容误导了或者没有读懂……这里说明一下：

本文写作的前几天，有关部门以“诱导未成年人自残、zs”为由封杀了歌曲《二重变革》，B 站删除了所有与该歌曲相关的稿件。本文即在讽刺这一事件。

本文与任何现实存在的音乐作品无关，请勿过度解读。 如果涉政了请管理手下留情先联系我删除，不要封禁我，谢谢。

Shell 在 1959 年提出了第一个复杂度低于 O(n^2) 的排序——希尔排序，这可以称为排序算法的第一次变革。本文将给排序算法带来再一次的变革。长期以来，基于比较的排序理论复杂度下界一直被认为是 O(n\log n)，甚至计算机科学的经典《算法导论》开篇就有这一结论的证明。但随着本文所描述的新排序算法的提出，这一下界被突破了。

这个算法的灵感来源于有关部门维护社会公序良俗，保证青少年健康安全上网的方式。

以下是这一排序算法的代码实现：

#include <iostream>
using namespace std;
int a[1000005], b[1000005];
int main() {
int n, lst=0; cin >> n; for (int i=1; i<=n; i++) cin >> a[i];
for (int i=1; i<=n; i++) if (a[i] >= b[lst]) b[++lst] = a[i];
for (int i=1; i<=lst; i++) cout << b[i] << ' ';
}

其正确性和复杂度是显然的。

由于它对计算机科学界的影响十分重大，我相信这一算法一定会获得屠零奖（注 1）。但这个奖不应该颁给我，而应该给首先提出了该算法的思想的有关部门，如果找不到有关人员，也应该颁给哔哩哔哩首先用代码实现了该算法的程序员。

这个算法在数论方面的一个应用：https://www.bilibili.com/video/BV1AS411w7pm

注 1：此处为笔误，并非有意为之。