介绍

珠排序是一种自然排序算法。无论是电子还是实物上的实现，珠排序都能在 O (n) 时间内完成；然而，该算法 在电子上的实现明显比实物要慢很多，并且只能用于对正整数序列进行排序 。并且，即使在最好的情况，该算法也需要 O (n^2) 的空间。

原理

当给定一个数组，数组里有多少个数字，就要有多少行；数组里最大的数字是几，就要准备多少根杆子。

准备就绪后，释放珠子，珠子按重力下落，就完成了排序。如果我们要允许珠子掉落，那么每行表示已排序的整数。第 1 行表示在集合中最大的数，而第 n 行表示最小的数。

允许珠子掉落的行为在物理意义上就是允许珠子从高的行掉落至低的行。如果被行 a 表示的值小于被行 a+1 表示的值，那么一些珠子就会从 a+1 掉落至 a；因为行 a 不包含足够的珠子防止珠从 a+1 行掉落，所以这一定会发生。

用机械设备实现的珠排序类似于计数排序；每一杆上的数字与那些在所有数中等于或大于该数字的数量相当。

复杂度

珠排序可以是以下复杂度级别：

• $O(1)$：即所有珠子都同时移动，但这种算法只是概念上的，无法在计算机中实现。
• $O(\sqrt{n})$：在真实的物理世界中用引力实现，所需时间正比于珠子最大高度的平方根，而最大高度正比于 n。
• $O(n)$：一次移动一行珠子，可以用模拟和数字的硬件实现。
• $O(S)$，S 是所有输入数据的和：一次移动一个珠子，能在软件中实现。

实现

JavaScript

/**
 * Bead Sort, also known as Gravity sort.
 *
 * This algorithm was inspired from natural phenomena and was designed keeping in mind objects (or beads) falling under
 * the influence of gravity.
 *
 * NOTE: It only works for arrays of positive integers.
 *
 * Wikipedia: https://en.wikipedia.org/wiki/Bead_sort
 */
export function beadSort (sequence) {
  /* Let's ensure our sequence has only Positive Integers */
  if (sequence.some((integer) => integer < 0)) {
    throw RangeError('Sequence must be a list of Positive integers Only!')
  }

  const sequenceLength = sequence.length
  const max = Math.max(...sequence)

  // Set initial Grid
  const grid = sequence.map(number => {
    const maxArr = new Array(max)

    for (let i = 0; i < number; i++) {
      maxArr[i] = '*'
    }

    return maxArr
  })

  // Drop the Beads!
  for (let col = 0; col < max; col++) {
    let beadsCount = 0

    for (let row = 0; row < sequenceLength; row++) {
      if (grid[row][col] === '*') {
        beadsCount++
      }
    }

    for (let row = sequenceLength - 1; row > -1; row--) {
      if (beadsCount) {
        grid[row][col] = '*'
        beadsCount--
      } else {
        grid[row][col] = undefined
      }
    }
  }

  /* Finally, let's turn our Bead rows into their Respective Numbers */
  return grid.map((beadArray) => {
    const beadsArray = beadArray.filter(bead => bead === '*')
    return beadsArray.length
  })
}

Python

def bead_sort(l):
    b = []
    l_len = len(l) - 1 
    index = 0 
    count = 0 
 
    while(any(l)):
        if l[index] != 0:
            count += 1
            l[index] -= 1
 
        if index == l_len:
            b.append(count)
            index = 0 
            count = 0 
        else:
            index += 1
 
    if count != 0:
        b.append(count)

    result = []
    for i, v in enumerate(b[:-1]):
        if v == b[i+1]:
            continue
        else:
            result.extend([i + 1 for _ in range(v - b[i + 1])])
 
    result.extend([len(b) for _ in range(max(b) - len(result))])
 
    return result

if __name__ == "__main__":
    print(bead_sort([2, 4, 1, 3, 3]))

CPP

#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;
    }
}

参考

• 珠排序 - 维基百科，自由的百科全书 (opens new window)