PHP radix sort を使用する手順の詳細な説明

今回は、PHP radix sort の使用手順について詳しく説明します。PHP radix sort を使用する際の 注意事項 は何ですか?実際のケースを見てみましょう。

基本的な考え方:

基数ソート(基数ソート)は「分散ソート」(分散ソート)に属し、その名の通り「バケットソート」またはビンソートとも呼ばれるキーの部分情報を使用します。基数ソート方法は安定したソートであり、その時間計算量は O (nlog(r)m) です。ここで、r は取得される基数です。 m はヒープの数です。ある時点では、基数ソート方法が他の安定性ソート方法よりも効率的です。

実際、このアイデアを要約することはできません。例を通して説明してみましょう:

基本的な解決策:

PS: ここで紹介する基数ソートでは、LSD (最下位ビットが最初) を使用します。もちろん、MSD (最も重要なものが最初) もあります。Baidu にアクセスして、それらの類似点と相違点を見つけることができます。

今、次の数値があるとします:

2 343 342 1 128 43 4249 814 687 654 3

基数ソートを使用して、小さい値から大きい値へ並べ替えます。

最初のステップは、値を参照するときに、最初に 1 桁の値に従って 0 から 9 までの番号が付けられたバケットに割り当てることです (前から後ろに訪問する場合、以下の手順は同じです):

0 :1 : 1
2 : 2 342
3 : 343 43 3
4 : 814 654
5 :
6 :
7 : 687
8 : 128
9 : 4249

価値観これらのバケットを再接続して次の順序を形成します:

1 2 342 343 43 3 814 654 687 128 4249

ステップ 3. 10 桁の値に従って、値を参照します (前から順に参照)戻って、次の手順は同じです)、それらを 0 から 9 までの番号が付けられたバケットに割り当てます:

0 : 1 2 31 : 814
2 : 128
3 :
4 : 342 343 43 4249
5 : 654
6 :
7 :
8 : 687
9 :

4 番目のステップは、これらのバケット内の値を再接続して次のシーケンスを形成することです:

1 2 3 814 128 342 343 43 4249 654 687

ステップ 5: 百の位の値に従って、値を参照するとき (前から後ろに参照する場合、以下の手順は同じです)、値を 0 から 9 までの番号が付いたバケットに割り当てます:

0 : 1 2 3 43 1 : 128
2 : 4249
3 : 342 343
4 :
5 :
6 : 654 687
7 :
8 : 814
9 :

6番目のステップは、内の値を再文字列化することです。これらのバケットを接続すると、

1 2 3 43 128 4249 342 343 654 687 814

という順序になります。 。 。 。 。 。誰もが次のステップに進むことができるはずです。実際、6 番目のステップに到達するまでに、ソートされていないものは 4249 個だけ残っています。

上記のステップから、多くのステップは同じなので、1、10、100、、、を制御するだけで済みます。

コードを見てみましょう。

アルゴリズムの実装:

//交换函数
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//获取数组中的最大数
//就像上面的例子一样，我们最终是否停止算法不过就是看数组中的最大值：4249，它的位数就是循环的次数
function getMax(array $arr){
  $max = 0;
  $length = count($arr);
  for($i = 0;$i < $length;$i ++){
    if($max < $arr[$i]){
      $max = $arr[$i];
    }
  }
  return $max;
}
//获取最大数的位数,最大值的位数就是我们分配桶的次数
function getLoopTimes($maxNum){
  $count = 1;
  $temp = floor($maxNum / 10);
  while($temp != 0){
    $count ++;
    $temp = floor($temp / 10);
  }
  return $count;
}
/**
 * @param array $arr 待排序数组
 * @param $loop 第几次循环标识
 * 该函数只是完成某一位（个位或十位）上的桶排序
 */
function R_Sort(array &$arr,$loop){
  //桶数组，在强类型语言中，这个数组应该声明为[10][count($arr)]
  //第一维是 0-9 十个数
  //第二维这样定义是因为有可能待排序的数组中的所有数的某一位上的只是一样的，这样就全挤在一个桶里面了
  $tempArr = array();
  $count = count($arr);
  //初始化$tempArr数组
  for($i = 0;$i < 10;$i ++){
    $tempArr[$i] = array();
  }
  //求桶的index的除数
  //如798个位桶index=(798/1)%10=8
  //十位桶index=(798/10)%10=9
  //百位桶index=(798/100)%10=7
  //$tempNum为上式中的1、10、100
  $tempNum = (int)pow(10, $loop - 1);
  for($i = 0;$i < $count;$i ++){
    //求出某位上的数字
    $row_index = ($arr[$i] / $tempNum) % 10;
    for($j = 0;$j < $count;$j ++){
      if(@$tempArr[$row_index][$j] == NULL){
        $tempArr[$row_index][$j] = $arr[$i];   //入桶
        break;
      }
    }
  }
  //还原回原数组中
  $k = 0;
  for($i = 0;$i < 10;$i ++){
    for($j = 0;$j < $count;$j ++){
      if(@$tempArr[$i][$j] != NULL){
        $arr[$k ++] = $tempArr[$i][$j];  //出桶
        $tempArr[$i][$j] = NULL;  //避免下次循环的时候污染数据
      }
    }
  }
}
//最终调用的主函数
function RadixSort(array &$arr){
  $max = getMax($arr);
  $loop = getLoopTimes($max);
  //对每一位进行桶分配（1 表示个位，$loop 表示最高位）
  for($i = 1;$i <= $loop;$i ++){
    R_Sort($arr,$i);
  }
}

呼び出しアルゴリズム:

$arr = array(2, 343, 342, 1, 128, 43, 4249, 814, 687, 654, 3);
RadixSort($arr);
var_dump($arr);

実行結果:

array(11) {
 [0]=>
 int(1)
 [1]=>
 int(2)
 [2]=>
 int(3)
 [3]=>
 int(43)
 [4]=>
 int(128)
 [5]=>
 int(342)
 [6]=>
 int(343)
 [7]=>
 int(654)
 [8]=>
 int(687)
 [9]=>
 int(814)
 [10]=>
 int(4249)
}

実際、私はかなり昔にこれらのコードを書きましたが、今日ブログを書いているときに、バケットが実際には次のとおりであることを発見しました。したがって、上記の R_Sort() 関数は複雑なので、array_push() と <a href="http://www.php.cn" target="_blank">array_shift<p style="text-align: left;">() </p></a> を使用してこのメ​​ソッドを書き換えます (もちろん、キューをシミュレートするには、提供されている splqueue を使用するのが最も適切です) SPL による、ここでは簡単にするために使用しません): R_Sort()函数复杂了，我们使用 array_push() 和 <a href="http://www.php.cn/wiki/1008.html" target="_blank">array_shift</a>() 来重写该方法（当然，要模拟队列的话，用 SPL 提供的 splqueue

function R_Sort(array &$arr,$loop){
  $tempArr = array();
  $count = count($arr);
  for($i = 0;$i < 10;$i ++){
    $tempArr[$i] = array();
  }
  //求桶的index的除数
  //如798个位桶index=(798/1)%10=8
  //十位桶index=(798/10)%10=9
  //百位桶index=(798/100)%10=7
  //$tempNum为上式中的1、10、100
  $tempNum = (int)pow(10, $loop - 1);
  for($i = 0;$i < $count;$i ++){
    //求出某位上的数字
    $row_index = ($arr[$i] / $tempNum) % 10;
    //入桶
    array_push($tempArr[$row_index],$arr[$i]);
  }
  //还原回原数组中
  $k = 0;
  for($i = 0;$i < 10;$i ++){
    //出桶
    while(count($tempArr[$i]) > 0){
      $arr[$k ++] = array_shift($tempArr[$i]);
    }
  }
}

基数ソート方法は安定したソート方法であり、その時間計算量は

O (nlog(r)m) です。ここで、r は取得された基数、m はヒープの数です。

この記事の事例を読んだ後は、この方法を習得したと思います。さらに興味深い情報については、php 中国語 Web サイトの他の関連記事に注目してください。

推奨読書:

php7 を使用して MongoDB を追加、削除、変更、クエリする手順の詳細な説明

PHPファクトリーメソッドのデザインパターン事例を詳しく解説

以上がPHP radix sort を使用する手順の詳細な説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。