PHP einfacher Auswahlsortieralgorithmus zum Lernen und Teilen

Dieser Artikel stellt hauptsächlich den PHP Simple Selection Sort-Algorithmus im Detail vor. Er hat einen gewissen Referenzwert. Ich hoffe, er kann jedem helfen.

Das Beispiel in diesem Artikel teilt den spezifischen Code der einfachen Auswahlsortierung in PHP als Referenz. Der spezifische Inhalt ist wie folgt

Grundidee:

Übergeben Sie n – Vergleich zwischen i Schlüsselwörtern, wählen Sie den Datensatz mit dem kleinsten Schlüsselwort aus n – i + 1 Datensätzen aus und tauschen Sie ihn mit dem i (1 <= i <= n) Datensatz aus und führen Sie dann n-1 Mal aus Die Sortierung der Datensatzreihenfolge ist 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);

Komplexitätsanalyse:

in In Durch den 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.

Verwandte Empfehlungen:

Detaillierte Erläuterung der Direktauswahlsortierung in der PHP-Sortieralgorithmusreihe

Detaillierte Erläuterung der Bucket-Sortierung im PHP-Sortieralgorithmus series_php skills

Detaillierte Analyse der Methode zur Implementierung des Hill-Sortieralgorithmus in PHP

Das obige ist der detaillierte Inhalt vonPHP einfacher Auswahlsortieralgorithmus zum Lernen und Teilen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!