dsal 珠子排序|一种自然排序算法

珠子排序|一种自然排序算法

原文:https://www . geesforgeks . org/bead-sort-natural-sorting-algorithm/

也被称为重力排序，这种算法的灵感来自自然现象，设计时考虑到物体(或珠子)在重力的影响下下落。

想法:正数是用一组像算盘上的珠子来表示的。

BSV

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

像上图一样，珠子从上到下代表以下数字:7，2，1，4，2。现在，假设这是珠子在时间 t = 0 的位置，并且随着每一秒的流逝，珠子将下落一级，只要它们下面没有珠子已经存在。在这种情况下，它们只是停留在它们下面的珠子上。(杆从左到右编号，水平从底部编号为 1、2、…………。n)
现在，在时间 t = 1 时，左侧前两根杆中的底部 2 个珠子停留在它们的位置上，而第二根杆的顶部的第二个珠子下降一个高度，停留在它下面的珠子上。等级 2 的第三和第四棒中的珠子下降到等级 1。同时，杆 3 至 7 中的珠子下降一级。现在，从上到下的数字变成:2，6，2，2，4。
这一直持续到时间 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;
}