今天本来想复习一下排序算法,在网上搜索的时候,偶然看到了一篇"珠排序"的论文,这种方法尝试直接以物理方式来思考排序问题。
把需要排序的每一个正整数分别看成一排珠子,比如有三个珠子就代表正整数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;
}