Radix Sort de l'algorithme de tri PHP

Cet article présente principalement l'algorithme de tri PHP Radix Sort. Il analyse en détail les principes, les méthodes de mise en œuvre et les compétences d'utilisation associées de l'algorithme de tri PHP radix avec des exemples. Les amis dans le besoin peuvent s'y référer

Le. L'exemple de cet article décrit l'algorithme de tri PHP Radix Sort. Je le partage avec vous pour votre référence. Les détails sont les suivants :

Le tri cardinal n'est pas mentionné dans "Dahua Data Structure", mais afin de rassembler les huit principaux algorithmes de tri, j'ai moi-même appris cet algorithme de tri. via Internet et je l'ai donné pour le partager avec tout le monde.

Idée de base :

Le tri par base est un "tri par distribution", également connu sous le nom de "méthode bucket" "(tri par bucket) ou bin sort, comme son nom l'indique, il alloue les éléments à trier dans certains "compartiments" via une partie des informations de valeur clé pour obtenir l'effet de tri. La méthode de tri par base est un tri stable, sa complexité temporelle est O (nlog. (r)m), où r est la base prise et m est le nombre de tas. Parfois, la méthode de tri par base est plus efficace que d'autres méthodes de tri par stabilité.

En fait, je ne peux pas résumer cette idée. Illustrons-la avec un exemple :

Solution de base :

PS : Le tri par base que nous présentons ici utilise le LSD (le chiffre le plus bas en premier) et bien sûr le MSD (le chiffre le plus élevé en premier). Allons sur Baidu pour découvrir les similitudes et les différences entre eux.

Supposons maintenant que nous ayons les nombres suivants :

2 343 342 1 128 43 4249 814 687 654 3

Nous utilisons le tri par base pour les trier Trier du plus petit au plus grand.

La première étape consiste à les attribuer d'abord à des buckets numérotés de 0 à 9 lors de la visite des valeurs (en visitant d'avant en arrière, les étapes suivantes sont les mêmes) en fonction des valeurs à un chiffre :

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

La deuxième étape consiste à reconnecter les valeurs dans ces buckets pour former la séquence suivante :

1 2 342 343 43 3 814 654 687 128 4249

La troisième étape, selon la valeur à dix chiffres, lors de la visite de la valeur (visite d'avant en arrière, les étapes suivantes sont les idem) Attribué aux buckets numérotés de 0 à 9 :

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

La quatrième étape consiste à ajouter les valeurs dans ces buckets Reconnecter les en série pour former la séquence suivante :

1 2 3 814 128 342 343 43 4249 654 687

La cinquième étape est, basée sur la valeur des chiffres des centaines, Lors de la visite des valeurs (visite d'avant en arrière, les étapes suivantes sont les mêmes), attribuez-les aux buckets numérotés de 0 à 9 :

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

La sixième étape consiste à reconnecter les valeurs dans ces buckets pour former la séquence suivante :

1 2 3 43 128 4249 342 343 654 687 814

. . . . . . Tout le monde devrait pouvoir franchir les prochaines étapes. En fait, au moment où nous atteignons la sixième étape, il n’en reste plus que 4 249 qui n’ont pas été triés.

D'après les étapes ci-dessus, de nombreuses étapes sont les mêmes, ce doit donc être un cycle. Nous n'avons besoin de contrôler que les unités, les dizaines, les centaines,,,,.

Regardons le code.

Implémentation de l'algorithme :

//交换函数
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);
  }
}

Algorithme d'appel :

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

Résultat d'exécution :

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)
}

En fait, j'ai écrit ces codes il y a pas mal de temps Oui, aujourd'hui, alors que j'écrivais un blog, j'ai découvert qu'un bucket est en fait une file d'attente, donc la fonction R_Sort() ci-dessus est compliquée. Nous utilisons array_push() et array_shift() pour réécrire la méthode (bien sûr, si vous le souhaitez. pour simuler une file d'attente, utilisez SPL Le splqueue fourni est le plus approprié, et je ne l'utiliserai pas ici par simplicité) :

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]);
    }
  }
}

Le La méthode de tri par base est une méthode de tri stable, sa complexité temporelle est O (nlog(r)m), où r est la base prise et m est le nombre de tas.

Recommandations associées :

Algorithme de tri PHP Quick Sort (Quick Sort) et son optimisation

Algorithme de tri PHP Merge Sort ( Merging Sort )

Algorithme de tri PHP Bubble Sort (Tri à bulles)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!