Radix-Sortierung eines PHP-Sortieralgorithmus

In diesem Artikel wird hauptsächlich der PHP-Sortieralgorithmus Radix Sort vorgestellt. Er analysiert die Prinzipien, Implementierungsmethoden und zugehörigen Verwendungsfähigkeiten des PHP-Radix-Sortieralgorithmus im Detail anhand von Beispielen.

Der Beispiel in diesem Artikel beschreibt den PHP-Sortieralgorithmus Radix Sort. Ich teile es Ihnen als Referenz mit:

Die Kardinalsortierung wird in „Dahua Data Structure“ nicht erwähnt, aber um die acht wichtigsten Sortieralgorithmen zusammenzustellen, habe ich diesen Sortieralgorithmus selbst gelernt über das Internet und gab es weiter, um es mit allen zu teilen.

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). Gehen wir zu Baidu, 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 Sequenz zu bilden:

1 2 3 814 128 342 343 43 4249 654 687

Der fünfte Schritt ist, basierend auf dem Hunderterstellenwert, 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, daher muss es sich um einen Zyklus handeln. 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);

Laufergebnis:

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 habe ich diese Codes schon vor einiger Zeit geschrieben Ja, als ich heute einen Blog schrieb, habe ich entdeckt, dass ein Bucket tatsächlich eine Warteschlange ist, daher ist die obige R_Sort()-Funktion kompliziert. Wir verwenden array_push() und array_shift() , um die Methode neu zu schreiben (natürlich, wenn Sie möchten). Um eine Warteschlange zu simulieren, verwenden Sie SPL. Das bereitgestellte splqueue ist am besten geeignet und 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]);
    }
  }
}

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

Verwandte Empfehlungen:

PHP-Sortieralgorithmus Quick Sort und seine Optimierung

PHP-Sortieralgorithmus Merge Sort (Merging Sort)

PHP-Sortieralgorithmus Bubble Sort (Bubble Sort)

Das obige ist der detaillierte Inhalt vonRadix-Sortierung eines PHP-Sortieralgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!