私は線形時間を使用してソートするいくつかのデータを持っているPHPプロジェクトでPHP

Question

でソートを数える、簡単なカウント並べ替え：

$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

あなたはalgorithmに正しく従っていません。これは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

あなたの質問とコメントを正しく理解していれば、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として$ V）$回数[$ V] ++; ...本当に

Answer 3

は（$sorted）それ自身の変数でソート$arを取得するには...意味がないん、それは非常に簡単です：私はあなたの質問だと思います

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

コメントは全体の画像を与えていません。

編集：あなたが特定のアルゴリズムを実装したかったことを明らかにした、私はそれが別の側面に焦点を当てるために価値があると思う（とあなたが実際に答えを得た、すでにそれは最初にそれを実装間違っていたいくつかのポイントが表示されます）今後

2つの（理論的な）アルゴリズムの複雑さを比較していますが、アルゴリズムの実装方法を脇に置いています。

PHPのsort()は - でも、「悪い」クイックに基づいて、数字によって他のいくつかのアルゴリズムの独自のPHPのユーザーコードの実装を追い越すだろう。

誤ったパラメータを比較したところです。関数の複雑さは、組み込みのPHP関数とあなたのユーザコードのある関数を比較するとあまり意味がありません。

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

承認された回答が間違っています。正しい：

$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; 
     } 
    } 
}