PHP 中的计数排序

Question

在一个 PHP 项目中，我有一些数据想要使用线性时间、简单计数排序进行排序：

$ar = array(7, 2, 0, 3, 8, 0, 12, 7, 6, 7);
$count = array();
foreach ($ar as $v)
    $count[$v]++;
$sorted = array();    
foreach ($count as $v => $c)
    for ($i = 0; $i < $c; $i++)
        $sorted[] = $v;

问题是上面的方法显然不起作用。 php 数组的工作方式更像是哈希图而不是数组。可以通过在最终循环之前插入 ksort($count) 来使代码正常工作，但是 ksort 的运行时间为 O(nlogn) ，这会破坏整个点。

有没有办法在php中进行线性时间排序？也许使用一些 array() 参数，或者一些完全不同的结构？

Answer 1

您没有正确遵循算法。这是 O(n)。

$ar = array(7, 2, 0, 3, 8, 0, 12, 7, 6, 7);
$count = array();
foreach ($ar as $v) {
    $count[$v] = isset($count[$v]) ? $count[$v] + 1 : 1;
}
$sorted = array();
$min = min($ar);
$max = max($ar);
for ($i=$min; $i<=$max; $i++) {
    if (isset($count[$i])) {
        for ($j=0; $j<$count[$i]; $j++) {
            $sorted[] = $i;
        }
    }
}

另请参阅 array_count_values()，或者计算计数循环内的最小值和最大值。

Answer 2

批准的答案是错误的。正确的：

$ar = array(7, 2, 0, 3, 8, 0, 12, 7, 6, 7);
$count = array();
foreach ($ar as $v) {
    $count[$v] = isset($count[$v]) ? $count[$v] + 1 : 1;
}
$sorted = array();
$min = min($ar);
$max = max($ar);
for ($i=$min; $i  <=   $max; $i++) {
    if (isset($count[$i])) {
        for ($j=0; $j<$count[$i]; $j++) {
            $sorted[] = $i;
        }
    }
}

Answer 3

如果我正确理解你的问题和评论，那么只使用 sort($count) 就可以了，不是吗？

$ar = array(7, 2, 0, 3, 8, 0, 12, 7, 6, 7);
$sorted = $ar;
sort($sorted);
var_dump($ar);
var_dump($sorted);

结果：

array(7,2,0,3,8,0,12,7,6,7);
array(0,0,2,3,6,7,7,7,8,12);

但我想知道 foreach($ar as $v)$count[$v]++; 是什么？确实……没有什么意义……

Answer 4

在代码中添加一些注释，以向您展示为什么这没有执行您认为应该执行的操作。

$ar = array(7, 2, 0, 3, 8, 0, 12, 7, 6, 7);

$count = array();
foreach ($ar as $v) {
    // add each number in $ar to $count.
    // the first number in $ar is 7, so 7 will be the first number in $count.
    // because 7 is in $ar 3 times, $count[7] == 3.
    $count[$v]++;
}

// the output of print_r will be very revealing:
print_r($count);
/*Array
(
    [7] => 3
    [2] => 1
    [0] => 2
    [3] => 1
    [8] => 1
    [12] => 1
    [6] => 1
)*/

$sorted = array();    
foreach ($count as $v => $c) {
    // the first entry: $count[7] == 3
    // so add 7 to $sorted 3 times.
    // the second entry: $count[2] == 1
    // so add 2 to $sorted 1 time.
    // etc.
    for ($i = 0; $i < $c; $i++) {
        $sorted[] = $v;
    }
}

这只是根据数字在第一个数组中的位置将数字分组在一起。

Answer 5

要在它自己的变量（$sorted）中获取已排序的$ar，这非常简单：

$sorted = $ar;
sort($sorted);

这让我认为您的问题和评论并没有给出完整的图片。

编辑：现在，在您澄清您想要实现特定算法之后（并且您实际上已经得到了一个答案，该答案显示了首先实现它的一些错误点），我认为值得关注另一个算法你的问题的一个方面：

你正在比较两种（理论）算法的复杂性，但你忽略了算法的实现方式。

PHP 的 sort() - 即使基于“糟糕的”快速排序，也会比您自己的 PHP 用户代码实现的其他算法高出。

您刚刚在这里比较了错误的参数。当您将内置 PHP 函数与用户代码中的某些函数进行比较时，函数的复杂性并没有说明太多。

Answer 6

$A = [1, 2, 2, 2, 1, 3, 3, 1, 2, 4, 5, 0, 0]; // example array
$m = max($A);
$count = array_fill(0, $m + 1, '0');
foreach ($A as $value) $count[$value] += 1;
       // next step is print the numbers 
$a = [];
foreach ($count as $key => $value) {
    for ($i = 0; $i < $value;) {
        array_push($a, $key);;
        $i++;
    }
}

var_dump($count); // print the sorted array
var_dump($a); // print the numbers (low to high)