logo标签列表

基数排序是如何工作的？

algorithmsortingradix-sort
40

我不知道为什么这对我来说很难理解。我查阅过维基页面、伪代码（以及实际代码），试图理解基数排序算法如何工作（与桶有关）。

我是在看错了吗？也许应该看看桶排序？有人能给我一个更简化的工作原理吗？供参考，这里是一个据说执行基数排序的代码块：

// Sort 'size' number of integers starting at 'input' according to the 'digit'th digit
// For the parameter 'digit', 0 denotes the least significant digit and increases as significance does
void radixSort(int* input, int size, int digit)
{
    if (size == 0)
        return;

    int[10] buckets;    // assuming decimal numbers

    // Sort the array in place while keeping track of bucket starting indices.
    // If bucket[i] is meant to be empty (no numbers with i at the specified digit),
    // then let bucket[i+1] = bucket[i]

    for (int i = 0; i < 10; ++i)
    {
        radixSort(input + buckets[i], buckets[i+1] - buckets[i], digit+1);
    }
}

我也看过非递归的解决方案：

void radixsort(int *a, int arraySize)
{
    int i, bucket[sortsize], maxVal = 0, digitPosition =1 ;
    for(i = 0; i < arraySize; i++) {
        if(a[i] > maxVal) maxVal = a[i];
    }

    int pass = 1; 
    while(maxVal/digitPosition > 0) {
        // reset counter 
        int digitCount[10] = {0};

        // count pos-th digits (keys) 
        for(i = 0; i < arraySize; i++)
            digitCount[a[i]/digitPosition%10]++;

        // accumulated count 
        for(i = 1; i < 10; i++)
            digitCount[i] += digitCount[i-1];

        // To keep the order, start from back side
        for(i = arraySize - 1; i >= 0; i--)
            bucket[--digitCount[a[i]/digitPosition%10]] = a[i];

        for(i = 0; i < arraySize; i++)
            a[i] = bucket[i];

        cout << "pass #" << pass++ << ": ";
        digitPosition *= 10;
    } 

}

具体来说，这行代码让我感到困扰。我已经试着用笔和纸仔细分析它，但仍然无法弄清它的作用：

   // To keep the order, start from back side
        for(i = arraySize - 1; i >= 0; i--)
            bucket[--digitCount[a[i]/digitPosition%10]] = a[i];
https://en.wikipedia.org/wiki/Radix_sort#Examples 里面有一个很好的例子。 - Eric
4个回答
102
在数学中，基数意味着进制，其中十进制将是基数10。想象一下你有一些数字，其中一些数字具有多个数字，例如：
5, 213, 55, 21, 2334, 31, 20, 430

为了简单起见，假设您想使用十进制基数（=10）进行排序。然后，您将通过单位分离数字，然后再将它们组合在一起；接下来，您将按十位分离数字，然后再将它们组合在一起；然后是百位，以此类推，直到所有数字都被排序。每次循环时，只需从左到右读取列表。您还可以想象将数字分成桶。这里是一个使用5, 213, 55, 21, 2334, 31, 20, 430的示例。
按单位分离：
- 零：20、430 - 一：21、31 - 二： - 三：213 - 四：2334 - 五：5、55
重新组合：20、430、21、31、213、2334、5、55
为了重新组合它们，首先阅读“零”桶，然后是“一”桶，依此类推，直到阅读“九”桶。
按十位数分离：
- 零：05 - 一：213 - 二：20、21 - 三：430、31、2334 - 四： - 五：55
重新组合：5、213、20、21、430、31、2334、55
按百位数分离：

  • 零：005，020，021，031，055

  • 一：

  • 二：213

  • 三：2334

  • 四：430

  • 五：

    合并：5、20、21、31、55、213、2334、430

千位分隔符：

  • 零：0005、0020、0021、0031、0055、0213、0430

  • 一：

  • 二：2334

  • 三：

  • 四：

  • 五：

    合并：5、20、21、31、55、213、430、2334

你现在完成了。我在Geekviewpoint上看到了一段不错的代码，分别使用Java和python编写。
9
哇！细节很多啊。你真的做得非常好。赞一个。+1 - kasavbere
8
我非常赞赏stackoverflow，也非常尊重寻求帮助的人们。 - Konsol Labapen
你能否解释一下，如果我们需要使用不同的基数，如何改变基数排序？例如，如果我们的最大数字是1 000 000 ^ 2，那么如果我猜测正确，我们可以使用基数256。但这会如何改变算法？ - frank17
我就喜欢有人用最简单易懂的方式解释事情，把它们分解到细胞层面！！ :D - NoobEditor
3
这是快速排序的基本流程。
第一轮：根据最低有效位（个位）使用计数排序对数组进行排序。注意，435在835之前，因为435在原始列表中出现在835之前。
第二轮：根据下一位数字（十位）使用计数排序对数组进行排序。注意，在此处608低于704，因为608在先前的列表中低于704，并且对于（835、435）和（751、453）同样适用。
第三轮：根据最高有效位（百位）使用计数排序对数组进行排序。注意，在此处435低于453，因为435在先前的列表中低于453，并且对于（608、690）和（704、751）同样适用。

更多细节您可以参考Codingeek的博客并且有清晰的理解。

2

想象一副扑克牌。首先按花色分成四堆，然后将这四堆放在一起，再根据点数分成13堆。将这些堆合并在一起，现在你就有了一副排序好的牌。

3
“按排名排序”作为基数排序的比喻是不恰当的，因为它暗示了比较和排序。例如：手动整理一副纸牌时，我会先放置一个4，然后是9，接着是5放在4之后但在9之前，再放一个3放在4之前等等... - user166390
@pst：请详细说明 - 它如何暗示排序？ - 500 - Internal Server Error
1
它在排序时意味着比较。类比模拟现实生活 - 在这种情况下，根据我所描述的操作，类比与其试图描述的内容不同。第一部分关于四堆的内容正是基数排序的核心，只有一个限制：这些堆总是按特定顺序排列。（而这个顺序是因为有人说它是这样，而不是因为牌组之间的任何比较。） - user166390
我猜这句话可以有两种理解方式（而且我对我的理解并不完全确定）：赞一个，但是如果能够更详细地阐述这个答案就更好了。 - user166390
我不知道。我认为如果它是这样的话会更好...你有13个等级的插槽/桶，你把卡片放到它们各自的插槽里，然后从最低的插槽到最高的插槽取回它们。哇啦。它们被排序了。你不需要进行任何比较。 - thang
0

也许我的代码可以帮到你 :)

这里是 Python 实现的基数排序代码：

import random,time

from random import randint

A=[random.randint(1,1212) for i in range(23)]


length = len(str(max(A)))

print(length) 

rang = 10

print(A)

start=time.time()

for i in range(length):

B = [[] for k in range(rang)]

for x in A:

    figure =x // (10**i) % 10

    B[figure].append(x)

A = []

for k in range(rang):

    A+=B[k]

end=time.time()

print(end-start)

print(A)
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接