40

我不知道为什么这对我来说很难缠住我的头。我浏览了 wiki 页面和伪代码(以及实际代码),试图了解基数排序算法是如何工作的(关于存储桶)。

我在这里寻找错误的东西吗?我应该研究桶排序吗?有人可以给我一个简化版的它是如何工作的吗?作为参考,这是一个据称执行基数排序的代码块:

// 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];
4

4 回答 4

103

在数学中,基数表示基数,十进制以 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

要将它们重新组合在一起,首先读取zeroes存储桶,然后读取存储ones桶,然后以此类推,直到您读取nines存储桶。

以十位分隔:

  • 零: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

你现在完成了。我在Javapython的 Geekviewpoint 上看到了一个很好的代码

于 2013-02-06T02:56:19.320 回答
3

这是快速排序的基本流程。

对于第一遍:我们使用计数排序根据最低有效位(1 位)对数组进行排序。请注意,435 低于 835,因为 435 在原始列表中出现在 835 之下。

对于第二遍:我们使用计数排序根据下一个数字(10 位)对数组进行排序。请注意,这里的 608 低于 704,因为 608 在上一个列表中出现在 704 之下,对于 (835, 435) 和 (751, 453) 也是如此。

对于第三遍:我们使用计数排序根据最高有效位(100 位)对数组进行排序。请注意,这里的 435 低于 453,因为 435 在上一个列表中出现在 453 以下,对于 (608, 690) 和 (704, 751) 也是如此。

更多细节可以参考codingeek上的这篇博客,有清晰的认识

于 2017-02-13T10:04:39.860 回答
2

想想一副纸牌。你首先把它按花色分成四堆。然后你把这四堆放在一起,现在根据排名分成 13 堆。把它们放在一起,你现在就有了一个分类好的牌组。

于 2013-02-05T21:54:25.250 回答
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)
于 2020-04-30T13:58:51.083 回答