今天本来想复习一下排序算法，在网上搜索的时候，偶然看到了一篇"珠排序"的论文，这种方法尝试直接以物理方式来思考排序问题。
把需要排序的每一个正整数分别看成一排珠子，比如有三个珠子就代表正整数3，有四个珠子则代表正整数4。
◯◯◯◯ → 正整数4
◯◯◯ → 正整数3
现在把这一系列珠子都向左/右对齐，水平放置，然后把每一列都串起来，用论文里的话就是，“就像算盘一样”。
之后把“算盘”立起来，只要做实验的地方有引力，这些珠子也可以自由滑动，那么在立起来之后马上就可以得到排序之后的答案了。
比如：3, 2, 4, 3
水平时：
◯◯◯
◯◯
◯◯◯◯
◯◯◯
立起来之后，珠子受引力而下滑↓
◯◯
◯◯◯
◯◯◯
◯◯◯◯
马上就排好了！
看到这里，想起了另一个可以通过物理方法解决的问题：
简化的题目：给出一个迷宫，一个地方进，另一个地方出，求路线。
按照常规的算法，大概就是DFS之类的。可是用物理方法怎么解呢？
这里就不得不提到Memristor(忆阻器)了。就如同它的名字所示，这货可以在断电之后保持之前的电阻，而之前的电阻则是由通过的电流量决定的。
有了这个东西，解决迷宫就方便了。简单来说就是在迷宫的每个路口放上一个忆阻器，然后在入口处接正极，出口处接负极，通电。接下来就只需要检查这些忆阻器的状态就行了。电流会帮我们找出至少一条路出来。
回到刚才的珠子上，当我准备写成程序的时候，突然发现这是一大坑：如果要按原文意思的“有三个珠子就代表正整数3”和“向左/右对齐，水平放置”的话，这二维数组得多大了？数据量和数据都很小还行，要是蹦个什么4294967295不就直接跪了。
或许直接用bit位来模拟珠子的有无？似乎比刚才可行，但在考虑节省空间的前提下，数据的范围依然不大。
那能不能把这些数转为二进制之后，看成珠子呢？
以刚才的3, 2, 4, 3为例：
011
010
100
011
嗯？这个明显不对吧，珠子放在哪里都是一样的，但是0, 1放在不同的位上它们的权制不一样啊。
可是总感觉这个“图”在哪里见过，如果从右往左，按每一列排序的话，这不就是二进制下的基数排序吗？
果断写了下来，貌似代码有点问题，先发上来大家看看吧，好久没坑算法了。
Code
#include <bitset>
using namespace std;
#define N 6
#define BIT 32
int main(int argc, const char * argv[]) {
bitset<BIT> a[N];
// 初始化长度为BIT位, 长度为N的数组
a[0] = 24; // 11000
a[1] = 19; // 10011
a[2] = 14; // 01110
a[3] = 2; // 00010
a[4] = 23; // 10111
a[5].set(); // 最后一个必须全部置位
for (int digit = 0; digit < BIT; digit++) {
int pivot = 0;
// 主元
for (int row = 0; row < N; row++) {
if (a[row][digit] == 1) {
pivot = row;
break;
}
}
// 前面已经是0的就不参与排序了
for (int row = pivot + 1; row < N; row++) {
if (a[row][digit] == 0) {
bitset<BIT> temp = a[row];
a[row] = a[pivot];
a[pivot] = temp;
pivot++;
if (pivot - row != 0) {
temp = a[pivot - 1];
for (int pos = pivot; pos < N; pos++) {
a[pivot - 1] = a[pivot];
}
a[row - 1] = temp;
}
}
}
}
for (int i = 0; i < N; i++) {
cout<<a[i].to_ullong()<<endl;
}
return 0;
}