BeadSort重力排序

最近在看好玩的算法, 重力排序是一个根据重力(Gravity)原理的自动排序, 这个排序是自然排序的一种, 非人为操作便可实现. 这种排序非常适合给小孩子解释排序的原理和自然需求.

上面这个图就是重力排序, 首先找出最大的数, 上图中是4, 然后设为m, 就是有m个pole(杆子), 这图就是4个杆子. 然后横着看, 每个row就是当前数字有几便有几个球. 比如row 1 (ary[0] = 2) 是2, 就是两个珠子.

然后让数字随着重力下落即可排序, 具体证明和复杂度wiki有. https://en.wikipedia.org/wiki/Bead_sort 可以看出这种排序用机械实现还可以, 用算法实现效率并不好.

#include <stdio.h>
#include <iostream>
#include <string.h>

using namespace std;

#define BEAD(i, j) beads[i*max + j]

void beadsort(int *a, int len)
{
    int max = a[0];
    for(int i = 1; i < len; i++)
    {
        if(a[i] > max)
        {
            max = a[i];
        }
    }

    unsigned int beads[max * len]; //positive int only
    memset(beads, 0, sizeof(beads));

    for (int i = 0; i < len; i++)
    {
        for(int j = 0; j < a[i]; j++)
        {
            BEAD(i, j) = 1;
        }
    }

    for(int j = 0; j < max; j++)
    {
        int sum = 0;
        for (int i = 0; i < len; i++)
        {
            sum += BEAD(i, j);// count the beads
            BEAD(i, j) = 0; // clear the post
        }
        
        for (int i = len - sum; i < len; i++)
        {
            BEAD(i, j) = 1; // gravity down 
        }
    }
    
    for (int i = 0; i < len; i++)
    {
        int j;
        for (j = 0; j < max && BEAD(i, j); j++); // j < max and BEAD(i, j) != null

        a[i] = j;
    }
}

上面是一个实现, 具体来说, 最难的地方在于如何实现珠子下落

    for(int j = 0; j < max; j++)
    {
        int sum = 0;
        for (int i = 0; i < len; i++)
        {
            sum += BEAD(i, j);// count the beads
            BEAD(i, j) = 0; // clear the post
        }
        
        for (int i = len - sum; i < len; i++)
        {
            BEAD(i, j) = 1; // gravity down 
        }
    }

代码首先计算一个pole上有几个珠子, 然后计算有几个空位, 把空位补上珠子,就是下落后的个数.

最后这个算法的弱点是只能sort正整数, 而且如果数字很离散, 那么效率就太低了