了解基数排序算法
Understanding Radix Sort Algorithm
我想了解这个基数排序算法是如何工作的。我是算法和位的新手，所以这对我来说并不容易。到目前为止，我已将这些注释添加到我的代码中以尝试使其更易于理解。我不确定我是否正确理解了这个概念，所以如果有人看到我的 comments/something 有任何问题，我理解不正确，请帮助我:)
还有谁能给我解释一下这行代码：mask = 1 << bit;
我评论的代码：
public static ArrayList<Integer> RadixSort(ArrayList<Integer> a)
//This method implements the radix sort algorithm, taking an integer array as an input
{
ArrayList<Integer> array = CopyArray(a);
//Created a new integer array called 'array' and set it to equal the array inputed to the method
//This was done by copying the array entered to the method through the CopyArray method, then setting the results of the method to the new empty array
Integer[] zerobucket = new Integer[a.size()];
Integer[] onebucket = new Integer[a.size()];
//Created two more integer arrays to act as buckets for the binary values
//'zerobucket' will hold array elements where the ith bit is equal to 0
//'onebucket' will hold array elements where the ith bit is equal to 1
int i, bit;
//Created two integer variables i & bit, these will be used within the for loops below
//Both i & bit will be incremented to run the radix sort for every bit of the binary value, for every element in the array
Integer element, mask;
//Created an integer object called element, this will be used to retrieve the ith element of the unsorted array
//Created an integer object called mask, this will be used to compare the bit values of each element
for(bit=0; bit<8; ++bit)
//Created a for loop to run for every bit of the binary value e.g.01000000
//Change from 8 to 32 for whole integers - will run 4 times slower
{
int zcount = 0;
int ocount = 0;
//Created two integer variables to allow the 'zerobucket' and 'onebucket' arrays to be increment within the for loop below
for(i=0; i<array.size(); ++i)
//Created a nested for loop to run for every element of the unsorted array
//This allows every bit for every binary value in the array
{
element = array.get(i);
//Set the variable 'element' to equal the ith element in the array
mask = 1 << bit;
if ((element & mask) == 0)
//If the selected bit of the binary value is equal to 0, run this code
{
zerobucket[zcount++] = array.get(i);
//Set the next element of the 'zerobucket' array to equal the ith element of the unsorted array
}
else
//Else if the selected but of the binary value is not equal to 0, run this code
{
onebucket[ocount++] = array.get(i);
//Set the next element of the 'onebucket' array to equal the ith element of the unsorted array
}
}
for(i=0; i<ocount; ++i)
//Created a for loop to run for every element within the 'onebucket' array
{
array.set(i,onebucket[i]);
//Appended the ith element of the 'onebucket' array to the ith position in the unsorted array
}
for(i=0; i<zcount; ++i)
//Created a for loop to run for every element within the 'zerobucket' array
{
array.set(i+ocount,zerobucket[i]);
//Appended the ith element of the 'zerobucket' array to the ith position in the unsorted array
}
}
return(array);
//Returned the sorted array to the method
}
我没有写这段代码，我得到它是为了尝试理解
我会倒序回答你的问题...
mask = 1 << bit;
根据优先规则，您可以这样写
mask = (1 << bit);
哪个更明显。取整数 1（0x01），将其左移一位，赋值给 mask。因此，如果位为 2，则掩码为 00000010（跳过前导零）。如果bit为4，mask为00001000，依此类推
掩码的原因是以下行：
if ((element & mask) == 0)
用来识别位位是1还是0。与位掩码进行 AND 运算的项将是零或非零，具体取决于位掩码中与 1 相同位置的位分别是 0 还是非零。
现在更复杂的问题。所讨论的算法是最低有效位基数排序，这意味着基数排序中排序值的传递从最低位到最高位（或者在软件整数的情况下，从右到左）位。
以下伪代码描述了您上面的代码：
array = copy (a)
for every bit position from 0 to radix // radix is 8
for each item in array
if bit at bit position in item is 0
put item in zeroes bucket
else
put item in ones bucket
array = ordered concatenation of ones bucket and zeroes bucket
return array
那么为什么这样做有效呢？您可以将其视为数组中项目的迭代加权排名。在所有其他位相同的情况下，具有 1 位的项目将比具有 0 位的项目更大（对项目进行排序）。每次传球对最终位置变得更加重要（加权排名）。这些二元排序的连续应用将导致更经常有 1 的项目更经常地被放置在 1 的桶中。每当一个项目留在 1 的桶中而其他项目不在时，与其他项目相比，该项目会提高其在 1 的桶中的相对位置，这些项目在未来的传递中也可能有 1。然后在 1 的桶中一致存在与位置的持续改进相关联，其逻辑极值将是数组中的最大值。
希望对您有所帮助。
我想了解这个基数排序算法是如何工作的。我是算法和位的新手，所以这对我来说并不容易。到目前为止，我已将这些注释添加到我的代码中以尝试使其更易于理解。我不确定我是否正确理解了这个概念，所以如果有人看到我的 comments/something 有任何问题，我理解不正确，请帮助我:)
还有谁能给我解释一下这行代码：mask = 1 << bit;
我评论的代码：
public static ArrayList<Integer> RadixSort(ArrayList<Integer> a)
//This method implements the radix sort algorithm, taking an integer array as an input
{
ArrayList<Integer> array = CopyArray(a);
//Created a new integer array called 'array' and set it to equal the array inputed to the method
//This was done by copying the array entered to the method through the CopyArray method, then setting the results of the method to the new empty array
Integer[] zerobucket = new Integer[a.size()];
Integer[] onebucket = new Integer[a.size()];
//Created two more integer arrays to act as buckets for the binary values
//'zerobucket' will hold array elements where the ith bit is equal to 0
//'onebucket' will hold array elements where the ith bit is equal to 1
int i, bit;
//Created two integer variables i & bit, these will be used within the for loops below
//Both i & bit will be incremented to run the radix sort for every bit of the binary value, for every element in the array
Integer element, mask;
//Created an integer object called element, this will be used to retrieve the ith element of the unsorted array
//Created an integer object called mask, this will be used to compare the bit values of each element
for(bit=0; bit<8; ++bit)
//Created a for loop to run for every bit of the binary value e.g.01000000
//Change from 8 to 32 for whole integers - will run 4 times slower
{
int zcount = 0;
int ocount = 0;
//Created two integer variables to allow the 'zerobucket' and 'onebucket' arrays to be increment within the for loop below
for(i=0; i<array.size(); ++i)
//Created a nested for loop to run for every element of the unsorted array
//This allows every bit for every binary value in the array
{
element = array.get(i);
//Set the variable 'element' to equal the ith element in the array
mask = 1 << bit;
if ((element & mask) == 0)
//If the selected bit of the binary value is equal to 0, run this code
{
zerobucket[zcount++] = array.get(i);
//Set the next element of the 'zerobucket' array to equal the ith element of the unsorted array
}
else
//Else if the selected but of the binary value is not equal to 0, run this code
{
onebucket[ocount++] = array.get(i);
//Set the next element of the 'onebucket' array to equal the ith element of the unsorted array
}
}
for(i=0; i<ocount; ++i)
//Created a for loop to run for every element within the 'onebucket' array
{
array.set(i,onebucket[i]);
//Appended the ith element of the 'onebucket' array to the ith position in the unsorted array
}
for(i=0; i<zcount; ++i)
//Created a for loop to run for every element within the 'zerobucket' array
{
array.set(i+ocount,zerobucket[i]);
//Appended the ith element of the 'zerobucket' array to the ith position in the unsorted array
}
}
return(array);
//Returned the sorted array to the method
}
我没有写这段代码，我得到它是为了尝试理解
我会倒序回答你的问题...
mask = 1 << bit;
根据优先规则，您可以这样写
mask = (1 << bit);
哪个更明显。取整数 1（0x01），将其左移一位，赋值给 mask。因此，如果位为 2，则掩码为 00000010（跳过前导零）。如果bit为4，mask为00001000，依此类推
掩码的原因是以下行：
if ((element & mask) == 0)
用来识别位位是1还是0。与位掩码进行 AND 运算的项将是零或非零，具体取决于位掩码中与 1 相同位置的位分别是 0 还是非零。
现在更复杂的问题。所讨论的算法是最低有效位基数排序，这意味着基数排序中排序值的传递从最低位到最高位（或者在软件整数的情况下，从右到左）位。
以下伪代码描述了您上面的代码：
array = copy (a)
for every bit position from 0 to radix // radix is 8
for each item in array
if bit at bit position in item is 0
put item in zeroes bucket
else
put item in ones bucket
array = ordered concatenation of ones bucket and zeroes bucket
return array
那么为什么这样做有效呢？您可以将其视为数组中项目的迭代加权排名。在所有其他位相同的情况下，具有 1 位的项目将比具有 0 位的项目更大（对项目进行排序）。每次传球对最终位置变得更加重要（加权排名）。这些二元排序的连续应用将导致更经常有 1 的项目更经常地被放置在 1 的桶中。每当一个项目留在 1 的桶中而其他项目不在时，与其他项目相比，该项目会提高其在 1 的桶中的相对位置，这些项目在未来的传递中也可能有 1。然后在 1 的桶中一致存在与位置的持续改进相关联，其逻辑极值将是数组中的最大值。
希望对您有所帮助。