Detaillierte Erläuterung der Schritte zur Verwendung der PHP-Radix-Sortierung

Dieses Mal erkläre ich Ihnen ausführlich die Schritte zur Verwendung der PHP-Radix-Sortierung. Was sind die Vorsichtsmaßnahmen bei der Verwendung der PHP-Radix-Sortierung?

Grundidee:

Radix-Sortierung ist eine „Verteilungssortierung“, auch bekannt als „Bucket-Methode“ (Bucket-Sortierung) oder Wie der Name schon sagt, ordnet die Bin-Sortierung die zu sortierenden Elemente bestimmten „Buckets“ zu, um einen Sortiereffekt zu erzielen. Die Radix-Sortiermethode ist eine stabile Sortierung, deren Zeitkomplexität O (nlog) ist (r)m), wobei r die genommene Basis und m die Anzahl der Heaps ist. Manchmal ist die Basissortierungsmethode effizienter als andere Stabilitätssortierungsmethoden.

Eigentlich kann ich diese Idee nicht zusammenfassen. Lassen Sie es uns anhand eines Beispiels veranschaulichen:

Grundlegende Lösung:

PS: Die hier vorgestellte Basissortierung verwendet LSD (niedrigste Ziffer zuerst) und natürlich MSD (höchste Ziffer zuerst). Sie können zu Baidu gehen, um die Ähnlichkeiten und Unterschiede zwischen ihnen herauszufinden.

Angenommen, wir haben jetzt die folgenden Zahlen:

2 343 342 1 128 43 4249 814 687 654 3

Wir verwenden die Radix-Sortierung, um sie zu sortieren Sortieren Sie vom Kleinsten zum Größten.

Der erste Schritt besteht darin, sie beim Besuch der Werte (Besuch von vorne nach hinten, die folgenden Schritte sind gleich) zunächst den Buckets mit den Nummern 0 bis 9 entsprechend den einstelligen Werten zuzuordnen:

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

Der zweite Schritt besteht darin, die Werte in diesen Buckets wieder zu verbinden, um die folgende Sequenz zu bilden:

1 2 342 343 43 3 814 654 687 128 4249

Der dritte Schritt, entsprechend dem zehnstelligen Wert, beim Besuch des Wertes (Besuch von vorne nach hinten, sind die folgenden Schritte die gleich) Zugeordnet zu den Buckets mit den Nummern 0 bis 9:

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

Der vierte Schritt besteht darin, die Werte in diesen Buckets erneut zu verbinden sie in Reihe, um die folgende Reihenfolge zu erhalten:

1 2 3 814 128 342 343 43 4249 654 687

Der fünfte Schritt, entsprechend dem Wert der Hunderterstelle , Wenn Sie die Werte besuchen (von vorne nach hinten, sind die folgenden Schritte gleich), weisen Sie sie den Buckets mit den Nummern 0 bis 9 zu:

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

Der sechste Schritt besteht darin, die Werte in diesen Buckets wieder zu verbinden, um die folgende Sequenz zu bilden:

1 2 3 43 128 4249 342 343 654 687 814

. . . . . . Jeder sollte in der Lage sein, die nächsten Schritte zu gehen. Tatsächlich sind bis zum sechsten Schritt nur noch 4249 übrig, die nicht sortiert wurden.

Von den oben genannten Schritten sind viele Schritte gleich, es muss also ein Zyklus sein. Wir müssen nur die Einer, Zehner, Hunderter kontrollieren.

Sehen wir uns den Code an.

Algorithmusimplementierung:

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

Aufrufalgorithmus:

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

Laufende Ergebnisse:

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

Eigentlich diese Ich habe den Code vor langer Zeit geschrieben. Als ich heute bloggte, habe ich festgestellt, dass ein Bucket tatsächlich eine Warteschlange ist, daher ist die obige R_Sort()-Funktion kompliziert. Wir verwenden array_push() und <a href="http%20:%20//www.php.cn/wiki/1008.html" target="_blank">array_shift<code><a href="http://www.php.cn/wiki/1008.html" target="_blank">array_shift</a>() () , um diese Methode neu zu schreiben (wenn Sie eine Warteschlange simulieren möchten, verwenden Sie natürlich die splqueue von SPL bereitgestellt ist am besten geeignet, ich werde es der Einfachheit halber hier nicht verwenden):

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

Die Radix-Sortiermethode ist eine stabile Sortierung und ihre zeitliche Komplexität beträgt O (nlog(r) m), wobei r die genommene Basis und m die Anzahl der Heaps ist.

Ich glaube, dass Sie die Methode beherrschen, nachdem Sie den Fall in diesem Artikel gelesen haben. Weitere spannende Informationen finden Sie in anderen verwandten Artikeln auf der chinesischen PHP-Website!

Empfohlene Lektüre:

Detaillierte Erläuterung der Schritte zum Hinzufügen, Löschen, Ändern und Abfragen von MongoDB in PHP7

Detaillierte Erläuterung des PHP-Factory-Methodenentwurfsmusters

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Schritte zur Verwendung der PHP-Radix-Sortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!