PHPの基数ソート方法

この記事では、主に PHP で基数ソートを実装する方法を紹介し、例の形で基数ソートの原理、実装方法、および関連する操作スキルを分析します。必要な友人は参考にしてください。 PHP で基数ソートを実装する方法。参考のために皆さんと共有してください。詳細は次のとおりです:

基数ソートは、キーワード内の各キーワードの値に基づいており、ソートされた N 個の要素に対して「配布」と「収集」の複数のパスを実行することによってソートされます。 。

具体的な例を使用して、基数ソートがどのように実行されるかを示しましょう。

初期シーケンスが R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100} であると仮定します。

どのアラビア数字でも、各桁の底は 0 ～ 9 で表されることがわかっています。

つまり、0 ～ 9 を 10 個のバケットとみなした方がよいでしょう。

まずシーケンスの一桁の数字に従って分類し、指定されたバケットに分割します。例: R[0] = 50、1 桁は 0、この数値を 0 番のバケットに保存します。

分類後、各バケツから0番から9番まで順番にすべての番号を取り出します。

この時、得られた系列は一桁の増加傾向を持つ系列となっています。

1 桁で並べ替えます: {50、30、0、100、11、2、123、543、187、49}。

次に、この方法で十の位と百の位を並べ替えると、最終的に並べ替えられた順序が得られます。

<?php
/**基数排序**/
/*
* 获取第几位上的数字
*
*百位数 = 2345%1000/100
*/
function getN($num,$N){
  $value = 10;
  for($i=1;$i<$N;$i++){
    $value = $value * 10;
  }
  $M = (int)(($num % $value /($value/10)));
  return $M;
}
/*
*/
function paixu($arr)
{
  $flag = 1;//该次位数上是否全为0标志位，全为0 flag=0
  for($M=1;$flag!=0;$M++)
  {
    $flag = 0;
    if($M > 1){
      $m = 0;
      for($j=0;$j<10;$j++){
        for($k=0;$k<count($b[$j]);$k++){
          if($b[$j][$k]!=0)
          $arr[$m++] = $b[$j][$k];//将容器中的数按序取出，进行下一次排序
        }
      }
      $b = array();//再给b附新值前要清空数组中原有的数据
    }
    for($i=0;$i<count($arr);$i++)
    {
      $thisNum = getN($arr[$i],$M);
      if($thisNum!=0) $flag = 1;
      $b[$thisNum][] = $arr[$i];//将数组中的数放入容器中
    }
  }
  print_r($arr);
  //var_dump($b);
}
/**基数排序**结束**/
paixu(array(65,3,45,6,7,8,31,100,1000,1234))
?>

実行結果:

コードをコピー

コードは次のとおりです:Array ( [0] => 3 [1] => 6 [2] => 7 [3] => 8 [4] => 45 [7] => 1000

基数ソートは、重複する数値を検索したり、間隔の数値を検索したりするためにも使用できます。

コードは重要ではありません (コードはまだ改善する必要があります)、アイデアが鍵です

関連する推奨事項:

PHPソートアルゴリズム実装の概要

PHPソートアルゴリズムHeap Sort

PHPソートアルゴリズムRadix Sort

以上がPHPの基数ソート方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。