Lernen des einfachen PHP-Auswahlsortieralgorithmus

In diesem Artikel wird hauptsächlich der PHP Simple Selection Sort-Algorithmus ausführlich vorgestellt, der einen gewissen Referenzwert hat.

Die Beispiele in diesem Artikel werden mit Ihnen geteilt. Der spezifische Code für PHP Simple Die Auswahlsortierung dient als Referenz. Der spezifische Inhalt lautet wie folgt:

Grundidee:

Durch n - i Vergleiche zwischen Schlüsselwörtern, von n - Wählen Sie den Datensatz mit dem aus kleinstes Schlüsselwort unter den i + 1 Datensätzen und tauschen Sie es mit dem i (1 <= i <= n) Datensatz aus. Nach n-1 Malen ist die Sortierung der Datensatzreihenfolge 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 Durch einen einfachen Auswahl- und Sortiervorgang werden weniger Datensätze verschoben. 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 Blog wird von „Dahua Data Structure“ verwiesen. Bitte kritisieren Sie mich nicht!

Das Obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, dass er für das Studium aller hilfreich sein wird. Ich hoffe auch, dass jeder die chinesische PHP-Website unterstützt.

Artikel, die Sie interessieren könnten:

Detaillierte Erläuterung der WeChat Tiaoyitiao PHP-Code-Implementierung

Erläuterung der Funktion zum Teilen von WeChat mit Moments und zum Aufzeichnen der Anzahl der von PHP implementierten Freigaben

Erklärung des PHP-Analyse-XML-Format-Datentoolklassenbeispiels

Das obige ist der detaillierte Inhalt vonLernen des einfachen PHP-Auswahlsortieralgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!