也称为重力排序，该算法的灵感来自自然现象，设计时要牢记受重力影响的物体(或珠子)。

理念：正数由一组珠子表示，就像算盘上的珠子一样。

使用 Bead Sort 对 {7, 2, 1, 4, 2} 进行排序。如果下面有空间，珠子会一颗颗地掉下来。

1. 如上图所示，珠子从上到下分别代表以下数字：7、2、1、4、2。现在，假设这是珠子在时间 t = 0 时每经过一秒的位置如果珠子下方没有珠子，珠子将下降一层。在这种情况下，它们只停留在它们下面的珠子上。(杆从左到右编号，级别从底部编号为 1、2、…….n。)
2. 现在，在时间 t = 1 时，左侧前两根杆中的底部 2 个珠子停留在其位置，而从第二根杆顶部开始的第二个珠子下降一个水平以停留在其下方的珠子上。第 2 层第 3 和第 4 杆的珠子下降到第 1 层。同时，第 3 到第 7 杆中的珠子下降了一层。现在，从上到下的数字变为：2、6、2、2、4。
3. 直到时间 t = 4，我们得到从上到下排序的数字序列，即：1、2、2、4、7。

为什么这么叫？

当人们试图想象这个算法时，它看起来好像珠子在重力的影响下下降到它们可以到达的最底层，从而导致一组珠子从地面向上按降序排列。如果您在可视化此操作时遇到问题，请访问此 链接

假设我们必须对数字 3、4、1、2 进行排序。上面的算法可以这样工作。

珠子分类工作

下面是代码，看代码之前自己尝试实现一下。

代码：

// C++ program to implement gravity/bead sort

#include <bits/stdc++.h>

using namespace std;

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

  // function to perform the above algorithm

void beadSort(int *a, int len)

{

    // Find the maximum element

    int max = a[0];

    for (int i = 1; i < len; i++)

        if (a[i] > max)

           max = a[i];

      // allocating memory

    unsigned char beads[max*len];

    memset(beads, 0, sizeof(beads));

      // mark the 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++)

    {

        // count how many beads are on each post

        int sum = 0;

        for (int i=0; i < len; i++)

        {

            sum += BEAD(i, j);

            BEAD(i, j) = 0;

        }

          // Move beads down

        for (int i = len - sum; i < len; i++)

            BEAD(i, j) = 1;

    }

      // Put sorted values in array using beads

    for (int i = 0; i < len; i++)

    {

        int j;

        for (j = 0; j < max && BEAD(i, j); j++);

          a[i] = j;

    }

}

  // driver function to test the algorithm

int main()

{

    int a[] = {5, 3, 1, 7, 4, 1, 1, 20};

    int len = sizeof(a)/sizeof(a[0]);

      beadSort(a, len);

      for (int i = 0; i < len; i++)

        printf("%d ", a[i]);

      return 0;

}

输出：

1 1 1 3 4 5 7 20

时间复杂度：该算法的运行时复杂度范围从 O(1) 到 O(S)(S 是输入整数的总和)，具体取决于用户的观点。最后，提出了三种可能的实现方式。

1. O(1) ：将所有珠子放在一起作为单个(同时)操作。这种复杂性无法在实践中实现。
2. O()：在使用重力的现实物理模型中，让珠子下落所需的时间与最大高度的平方根成正比，最大高度与 n 成正比。
3. O(n) ：由于行数等于 n，因此将帧中的珠子行(代表一个数字)丢弃为一个不同的操作。
4. O(S) : 将每个珠子作为单独的操作丢弃，因为 S 是所有珠子的总和。

与 Pigeonhole 排序 一样，珠排序是不寻常的，因为在最坏的情况下它可以比 O() 更快的性能最坏情况下的比较排序。这是可能的，因为珠排序的键始终是一个正整数，并且珠排序利用了它的结构。

空间复杂性：珠粒分类是废物处理的记录保持者。额外内存的成本超过了存储阵列本身的成本。它的内存复杂度是 O()

参考资料：

• https://www.wikiwand.com/en/Bead_sort
• https://kukuruku.co/post/bead-sort/
• https://rosettacode.org/wiki/Sorting_algorithms/Bead_sort
• https://www.cs.auckland.ac.nz/~mjd/misc /BeadSort5.pdf