Ausführliche Erklärung des einfachen PHP-Auswahlsortierfalls

Dieses Mal werde ich Ihnen den Fall der einfachen Auswahlsortierung ausführlich erläutern und welche Vorsichtsmaßnahmen für die einfache PHP-Auswahlsortierung gelten. Das Folgende ist ein praktischer Fall: Werfen wir einen Blick darauf.

Grundidee:

Wählen Sie den Schlüssel aus n - i + 1 Datensätzen bis n - i Vergleichen zwischen Schlüsselwörtern. Der Datensatz mit dem kleinsten Wort wird mit dem i-ten (1 <= i <= n) Datensatz ausgetauscht. Nach n-1-maliger Ausführung ist die Sortierung der Datensatzfolge 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:

Beim einfachen Auswahlsortierungsprozess ist die Anzahl der zu verschiebenden Datensätze 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.

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 zur Verwendung des PHP-Schnellsortierungsalgorithmus

Detaillierte Erläuterung der Schritte zur Verwenden Sie die PHP-Radix-Sortierung

Das obige ist der detaillierte Inhalt vonAusführliche Erklärung des einfachen PHP-Auswahlsortierfalls. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!