大概四五月份的时候我做了一个梦，其实很短，应该也算不上一个梦，就梦见几个小孩玩什么孔明锁之类的东西，然后脑内神叨叨地闪过一句话 “一切都来自于小孩的玩具” ，然后我就醒了，我就想这些益智游戏可能对我会产生什么启发，然后一 波 狂 想 之 后 [此处省略200字] ，我就想到了这个排序算法

至于具体思路历程，我懒得写了，毕竟还要画图，有空再发吧[doge]

过程

然后这个新排序也是非常简单啊。众所周知，计算机里面整数毕竟都是用二进制存的，所以待会我就干脆把所有待排序的数字都写成二进制的。而且为了简化，这里都是无符号整型，也就是说这些数都没有负号。其实这个排序也能排有符号整数和浮点数的，一会再说怎么整

先上图

这是排序的第一步，左边是一开始的原始序列，每行都是个二进制正数，一共8行，也就是说一共8个正数。右边是第一步操作之后的序列
（相信你已经看懂了，恭喜你学会了这个排序，本文章到此结束）

其实这一步就是把第一位是0的数全部移到上面，第一位是1的数全部移到下面，这个操作是O(n)的，你可以用类似归并的算法或者类似于快排里面的分割操作做到这个，显然现在这些数字被分成了两组，黄框里的数第一位是0，蓝框里面是1。显然黄框里面的数字现在都比蓝框里的小。之后我们只要把黄框里的数字排好序，再把蓝框也排好，就完事了

感觉我废话好多。其实我本来就只想做个一目了然的动画，就不必大费口舌了，可惜不会

如果把这个K换成J，这波叫绝杀，可惜换不得。——五五开

然后我们把原来黄框里面的数操作一下，下一步是这样的

由于右边没空间画了，所以才把右上黄框里的一堆数复制到左下角。现在排序左下角的序列，用一样的套路，只需要康康第二个数位，从0到1分一下就好了。

后面就不解释了，你只要以此类推，用同样的方法把每个部分排一下，就能排完了，毕竟每一步都差不多，都是带 0 的数移上面，带 1 的移下面

这是全过程（懒得画 图2 的箭头了，因此十分抽象(bushi)）

啪的一下，很快啊，然后每个部分全部排好了

解释完了，代码见此

#include <cstdio>
#include <algorithm>
enum {N = 10000000};
unsigned int a[N];

inline int scan() //输入：先输入数字n，再输入n个数待排序
{
    int n;
    std::scanf("%d", &n);
    for (int i = 0; i < n; i++)
        std::scanf("%u", a + i);
    return n;
}

inline void print(const int &n) //输出
{
    int i = 0;
    do {
        std::printf("%u ", a[i++]);
    } while (i < n);
}

void bit_sort(const int bit, unsigned * const start, unsigned * const end) //bit < 32
{
    if (start >= end - 1 || bit < 0) return;
    unsigned * const mid = std::partition(start, end, [&bit](const unsigned &x){return !(x & 1u << bit);});//这个partition()就是一个分组函数，后面会解释
    bit_sort(bit - 1, start, mid);
    bit_sort(bit - 1, mid, end);
}

int main()
{
    int n = scan();//输入
    bit_sort(31, a + 0, a + n);//排序：把区间[a + 0, a + n)间的数进行排序
    print(n);//输出
    return 0;
}

这个代码要求C++11，并且要在编译选项里面加一个-std=c++11如图

（反正vscode是要手动加的，Dev C++只要在编译选项里面改一下就行了）

代码里那个partition()是啥？

partition()就是一个在algorithm头文件里面定义的STL函数，原函数声明如下

template<class BidirectionalIterator, class Predacate>
BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);

其实你并不用看懂上面是什么意思，反正这个函数的用法大概就是像这样：partition(start, end, pred)。其中start和end是指针，pred是你定义的一个函数的函数名：这个pred函数应当只接受一个参数，并返回一个bool值。然后partition函数会对区间[start, end)里的元素进行分组，把所有pred(x)返回true的元素都放在区间前面

在这里我是这么用的（已简化，其实原代码很多词都是没有用的）

std::partition(start, end, [bit](unsigned x){return !(x & 1u << bit);});

这个 [bit](unsigned x){return !(x & 1u << bit);} 是一个lambda表达式（C++11内容），相当于一个无名函数，接受一个参数 x ，返回表达式 !(x & 1u << bit) 的值。'bit' 是在外面定义的局部变量，但是我们要在lambda里面用，所以你必须在中括号[]里写'bit'，把'bit'的值捞进lambda里

复数和浮点数

如果你知道负数和浮点数的二进制是怎么存的，那把上面代码稍微改一下就好了，很简单的，这个问题就留给你了

不就是懒得写吗，淦

复杂度

假设用这个算法排序unsinged int, 这个算法每次进行分类的操作复杂度为$O(n)$，然后每个数一共有 $32 = log_2$MAX_INT 位，也就是说一共每个数被分32次，相当于 $log_2n$次，所以一乘就是这个排序的复杂度$nlogn$，不过这应该算最坏情况，因为很多数就是排了两三次就确定位置了
然后就有人问了，你这不就$nlogn$吗，怎么就最快了。那你看下一段不就好了

这是什么憨批写作方式

为 啥 更 快 （十分笼统的解释）

其实这个排序更别的排序最大的区别，就在于 以前的排序都基于用<比较大小的，但是这个不用这样比，这个只要把每一位都读一遍就好了。用<比较大小的话，你要从头开始把两个数各个数位都比一边，才能比出这两个数的大小。比如00000001和00000101，正常的话你应该从最左边开始比，一直比到第六位你才能确定第二个数更大。然后，以前排序复杂度最快都是$O(nlogn)$，相当于比较了$nlogn$次int，比较一次int就要比较int的$log_2n = 32$个数位（n指int最大值），也就是说比较了$n(log_2n)^2$次的数位。但是现在这个新排序，理论上每个数位只需要被访问一次，一共有$nlog_2n$个数位，也就是在这一方面其实可以快了32倍。然而，理论虽是如此，“每个数位只需要被访问一次”在C++上 好 像 打不出来这样的代码，毕竟C++编这个算法只能用各种位运算，但这种位运算都是横着读的，实际上按照上面示意图我们只想直接竖着读，所以这一段的优化并不能实现，所以现实很打脸 （成功证明自己标题党是不是） 不过我觉得汇编应该可以做到(确信

然而，令人高兴的是，即使我的上述分析做不到，这个排序依旧比直接sort()快了几毫秒
新算法的评测 直接sort的评测

又试了几遍好像又变慢了，可能就是运气吧(逃
不过好歹比别人手打快排跑个1秒要好，要知道，快排最差情况复杂度可是$O(n^2)$

其实还想讲我当时想出来的另一种排序的，也和二进制有关，但是单讲一个就这么长了（长吗？），另一个就懒得打了，这就去摸鱼

先提一下，另一个排序还跟二叉树有关，灵感来源是这个（略有删改）：

你们可以先猜起来了[doge]
(提示：你有没有感觉这个爷上爷、爷下爷很像左子树和右子树？又很像1和0？我就觉得这点提示已经够了，跑喽)

（我是不是应该发洛谷日报才对）