Php二进制基数排序实现

Question

我试图用二进制实现基数排序，因为我想检查比特移位操作的速度是否与所需的步数相平衡。我的计数排序似乎有效，但只要我通过了几次基数排序，结果就会中断。非常感谢您的帮助。

/*
* bits is to store the value of the current digit for each number in the input array
*/
function countSort(&$arr, $digit) {
$bits = $output = array_fill(0, NB_ELEMS, 0);
$count = [0,0];

// Store count of occurrences in count[]  
for ($i = 0; $i < NB_ELEMS; $i++) {
$nb = $arr[$i];
$bit = ($nb >> $digit) & 1;
$bits[$i] = $bit;
$count[$bit]++;
}
// Cumulative count
$count[1] = NB_ELEMS;
// Rearranging
for ($i = 0; $i < NB_ELEMS; $i++) {
$nb = $arr[$i];
$bit = $bits[$i];
$output[$count[$bit] - 1] = $nb;
$count[$bit]--;
}
// Switch arrays
$arr = $output;
}
function radixSort(&$arr, $nb_digits) {      
// Do counting sort for every binary digit
for($digit = 0; $digit < $nb_digits; $digit++) {
countSort($arr, $digit);
}
}
$tab = [4,3,12,8,7];
$max_value = max($tab);
$nb_digits = floor(log($max_value, 2)) + 1;
radixSort($tab, $nb_digits);

Answer 1

好吧，多亏了一位朋友，我发现了我的问题：我使用的计数排序实现使用计数器作为顶部索引来堆叠相同的数字，然后递减。计数排序也可以(所以一次迭代(，但当你在基数排序中使用它时(多次计数排序迭代(，它会打乱所有东西。

所以我用了一种方法，你把计数器向右移动一次，这就给了n+1位的起点，然后递增

轰，你可以走了。

function countSort2(&$arr, $digit) {
$bits = $output = array_fill(0, NB_ELEMS, 0); // output array  
$count = [0,0];

// Store count of occurrences in count[]  
for ($i = 0; $i < NB_ELEMS; $i++) {
$nb = $arr[$i];
$bit = ($nb >> $digit) & 1;
$bits[$i] = $bit;
$count[$bit]++;
}
// Cumulative count shifted
$count[1] = $count[0];
$count[0] = 0;
// Rearranging
for ($i = 0; $i < NB_ELEMS; $i++) {
$nb = $arr[$i];
$bit = $bits[$i];
$output[$count[$bit]] = $nb;
$count[$bit]++;
}
// Switch arrays
$arr = $output;
}  

我还做了一些测试(1M个项目，最大值1M，100次迭代(，以及一种存储值而不是计数值的方法，然后合并的速度似乎是原来的两倍(紧接着就起作用了(。无论如何，这两种方法都远远低于本机排序性能。任何评论都感谢

function byDigitSortArrayMerge(&$arr, $digit) {
$output = array_fill(0, NB_ELEMS - 1, 0); // output array  
$bits = array_fill(0, NB_ELEMS - 1, 0); // output array
$by_bit = [[], []];

// Store count of occurrences in count[]  
for ($i = 0; $i < NB_ELEMS; $i++) {
$nb = $arr[$i];
$bit = ($nb >> $digit) & 1;
$by_bit[$bit][] = $nb;
}
$arr = array_merge($by_bit[0], $by_bit[1]);
}