PHP-Sortieralgorithmus Einfache Auswahlsortierung (Einfache Auswahlsortierung)

In diesem Artikel wird hauptsächlich der PHP-Sortieralgorithmus Simple Selection Sort vorgestellt. Er analysiert die Prinzipien und zugehörigen Implementierungstechniken des Simple Selection Sort-Algorithmus im Detail in Form von Beispielen.

Das Beispiel in diesem Artikel beschreibt den PHP-Sortieralgorithmus Simple Selection Sort. Teilen Sie es wie folgt mit allen als Referenz:

Grundidee:

Durch n - i Vergleiche zwischen Schlüsselwörtern, von n - Select den Datensatz mit dem kleinsten Schlüsselwort unter den i + 1 Datensätzen und tauschen Sie ihn mit dem i (1 <= i <= n) Datensatz aus. Nach n-1-maliger Ausführung ist die Sortierung der Datensatzsequenz abgeschlossen.

Algorithmusimplementierung:

<?php
//简单选择排序
//交换函数
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//简单选择排序算法
function SelectSort(array &$arr){
  $count = count($arr);
  for($i = 0;$i < $count - 1;$i ++){
    //记录第$i个元素后的所有元素最小值下标
    $min = $i;
    for($j = $i + 1;$j < $count;$j ++){
      if($arr[$j] < $arr[$min]){
        $min = $j;
      }
    }
    if($min != $i){
      swap($arr,$min,$i);
    }
  }
}
$arr = array(9,1,5,8,3,7,4,6,2);
SelectSort($arr);
var_dump($arr);

Laufergebnis:

array(9) {
 [0]=>
 int(1)
 [1]=>
 int(2)
 [2]=>
 int(3)
 [3]=>
 int(4)
 [4]=>
 int(5)
 [5]=>
 int(6)
 [6]=>
 int(7)
 [7]=>
 int(8)
 [8]=>
 int(9)
}

Komplexitätsanalyse:

Im einfachen Auswahlsortierungsprozess wird die erforderliche Bewegung von Datensätzen ermittelt Die Häufigkeit ist relativ gering. Im besten Fall ist der Ausgangszustand der zu sortierenden Datensätze bereits in positiver Reihenfolge und es besteht keine Notwendigkeit, die Datensätze zu verschieben.

Im schlimmsten Fall ist der Anfangszustand der zu sortierenden Datensätze, dass der erste Datensatz der größte ist und die nachfolgenden Datensätze in aufsteigender Reihenfolge angeordnet werden, dann die Anzahl der Datensätze, die sortiert werden müssen bewegt ist höchstens 3 (n-1). Die Anzahl der bei der einfachen Auswahlsortierung erforderlichen Vergleiche hat nichts mit der Anordnung der zu sortierenden Datensatzreihenfolge im Ausgangszustand zu tun. Wenn i=1, sind n-1 Vergleiche erforderlich; wenn i=2, sind n-2 Vergleiche erforderlich usw., die Gesamtzahl der erforderlichen Vergleiche beträgt (n-1)+(n-2)+ …+2 +1=n(n-1)/2, das heißt, die zeitliche Komplexität der Vergleichsoperation beträgt O(n^2) und die zeitliche Komplexität der Verschiebungsoperation beträgt O( n) .

Einfache Auswahlsortierung ist eine instabile Sortierung.

Auf diesen Artikel wird von „Dahua Data Structure“ verwiesen. Er wird hier nur zum späteren Nachschlagen aufgezeichnet.

Verwandte Empfehlungen:

PHP-Sortieralgorithmus Straight Insertion Sort (Straight Insertion Sort)

PHP-Sortieralgorithmus Hill Sort (Shell Sort)

Das obige ist der detaillierte Inhalt vonPHP-Sortieralgorithmus Einfache Auswahlsortierung (Einfache Auswahlsortierung). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!