按二进制位的基数排序

今天本来想复习一下排序算法,在网上搜索的时候,偶然看到了一篇"珠排序"的论文,这种方法尝试直接以物理方式来思考排序问题。

把需要排序的每一个正整数分别看成一排珠子,比如有三个珠子就代表正整数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 <iostream>
#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;
}

 

声明: 本文为0xBBC原创, 转载注明出处喵~

发表评论

电子邮件地址不会被公开。 必填项已用*标注