PHPで基数ソートを実装する方法の説明-PHPチュートリアル-php.cn

PHPで基数ソートを実装する方法の説明

jacklove

リリース： 2023-04-02 20:58:02

オリジナル

1654 人が閲覧しました

この記事では、主に 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] => 31 [5] => 45 [6 ] => 65 [7] => 100 [8] => 1000 [9] => 1234 )

基数ソートも使用できます重複を見つけるには番号、検索間隔番号など。

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

PS : 並べ替えデモンストレーションツールに関する別の記事を参考にしてください:

挿入/選択/バブル/マージ/ヒル/クイックソートアルゴリズムプロセスツールのオンラインアニメーションデモンストレーション:

http://tools.jb51.net/aideddesign/paixu_ys

興味があるかもしれない記事: