如何基数排序工作？ [英] How does Radix Sort work?
问题描述
我不知道为什么会这样难受，周围包裹我的头。我已经通过维基页面看了看，和伪code（以及实际的code）试图了解基数排序算法的工作（相对于桶）。
我是否寻找到错误的东西在这里吗？我应该寻找到桶排序可能？有人可以给我它是如何工作的一个简单化的版本？作为参考，在这里是codeblock将是的按说的执行基数排序：
//排序尺寸编号整数开始在输入根据digit'th位
//对于参数数字，0表示至少显著数字和随意义不
无效radixSort（INT *输入，诠释大小，INT位）
{
如果（大小== 0）
返回;
INT [10]水桶; //假设小数
//排序数组中的位置，同时跟踪桶开始指数。
//如果桶[i]的意思是空的（我没有数字在指定的数字），
//然后让桶[I + 1] =斗[I]
对（INT I = 0; I＆小于10; ++ i的）
{
radixSort（输入+水桶[I]，水桶[I + 1] - 料斗[I]中，数字+ 1）;
}
}
和我已经看了非递归解决方案还：
无效radixsort（INT *一，诠释ARRAYSIZE）
{
INT I，斗[sortsize]，MAXVAL = 0，digitPosition = 1;
对于（i = 0; I＆LT; ARRAYSIZE;我++）{
如果（A [1]≥MAXVAL）MAXVAL = A [1];
}
INT通= 1;
而（MAXVAL / digitPosition大于0）{
//计数器复位
INT digitCount [10] = {0};
//计数POS个数字（密钥）
对于（i = 0; I＆LT; ARRAYSIZE;我++）
digitCount [A [1] / digitPosition％10] ++;
//累计数
为（ⅰ= 1; I＆小于10;我+ +）
digitCount [I] + = digitCount [I-1];
//为了保持秩序，从背面开始
对于（I = ARRAYSIZE - 1; I＆GT; = 0;我 - ）
斗[ - digitCount [A [1] / digitPosition％10] = A [1];
对于（i = 0; I＆LT; ARRAYSIZE;我++）
A [1] =斗[I]
COUT＆LT;＆LT; 通过＃＆LT;＆LT;通过++＆LT;＆LT; ：;
digitPosition * = 10;
}
}
具体而言，此行是给我麻烦。我试图通过它走与笔和纸，但我仍然无法弄清楚这是什么做的：
//为了保持秩序，从背面开始
对于（I = ARRAYSIZE - 1; I＆GT; = 0;我 - ）
斗[ - digitCount [A [1] / digitPosition％10] = A [1];
在数学，基数是指基地，在那里小数将是基地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
您现在完成了。我看到了一个不错的code这对Geekviewpoint无论是在的Java 和的python
I don't know why this is so hard for me to wrap my head around. I've looked through the wiki pages, and pseudo code (as well as actual code) trying to understand how radix sort algorithms work (with respect to buckets).
Am I looking into the wrong thing here? Should I be looking into bucket sort maybe? Can someone give me a dumbed down version of how it works? For reference, here is a codeblock that supposedly performs a radix sort:
// 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);
}
}
And I've looked at non-recursive solutions also:
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;
}
}
Specifically, this line is giving me troubles. I've tried walking through it with pen and paper, but I still can't figure out what this is doing:
// To keep the order, start from back side
for(i = arraySize - 1; i >= 0; i--)
bucket[--digitCount[a[i]/digitPosition%10]] = a[i];
In mathematics, radix means base, where decimal would be base 10. Imagine you have numbers some of which having more than one digits like
5, 213, 55, 21, 2334, 31, 20, 430
For simplicity, say you want to use the decimal radix (=10) for sorting. Then you would start by separating the numbers by units and then putting them together again; next you would separate the numbers by tens and then put them together again; then by hundreds and so on until all the numbers are sorted. Each time you loop, just read the list from left to right. You can also imagine you are separating the numbers into buckets. Here is an illustration using 5, 213, 55, 21, 2334, 31, 20, 430
Separate by units:
zeros: 20, 430
ones: 21, 31
twos:
threes: 213
fours: 2334
fives: 5, 55
Back together: 20, 430, 21, 31, 213, 2334, 5, 55
To put them back together, first read the zeroes bucket, then the ones bucket, then so on, until you read the nines bucket.
Separate by tens:
zeros: 05
ones: 213
twos: 20, 21
threes: 430, 31, 2334,
fours:
fives: 55
Back together: 5, 213, 20, 21, 430, 31, 2334, 55
Separate by hundreds:
zeros: 005, 020, 021, 031, 055
ones:
twos: 213
threes: 2334
fours: 430
fives:
Back together: 5, 20, 21, 31, 55, 213, 2334, 430
Separate by thousands:
zeros: 0005, 0020, 0021, 0031, 0055, 0213, 0430
ones:
twos: 2334
threes:
fours:
fives:
Back together: 5, 20, 21, 31, 55, 213, 430, 2334
You are now done. I saw a nice code for this on Geekviewpoint both in Java and in python
这篇关于如何基数排序工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
