Detaillierte Analyse des Auswahlsortierungsalgorithmus

Auswahlsortierung

Auswahlsortierung ist einer der stabilsten Sortieralgorithmen. Bei seiner Verwendung gilt: Je kleiner die Datengröße, desto besser. Theoretisch ist die Auswahlsortierung möglicherweise auch die gebräuchlichste Methode, an die die meisten Menschen beim Sortieren denken.

Selection Sort ist ein einfacher und intuitiver Sortieralgorithmus. So funktioniert es:

Durchlaufen Sie ein Array und ermitteln Sie dabei den Maximalwert und seine Position im Array. Dann „tauschen“ Sie die Position der Einheit mit dem Maximalwert mit der letzten Einheit des Arrays aus. Danach muss der Maximalwert im Array an der letzten Position platziert werden.

Durchlaufen Sie die verbleibenden Daten im obigen Prozess weiter und machen Sie dasselbe. Dann kann der Maximalwert des verbleibenden Teils auch an der letzten Position des verbleibenden Teils platziert werden – es ist die vorletzte Position als Ganzer Ort.

Und so weiter. . . . . .

Bild:

22

Originalarray

原始数组	18	22	12	15	23	9
第一趟	18	22	12	15	9	23
第二趟	18	9	12	15	22	23
第三趟	15	9	12	18	22	23
第四趟	12	9	15	18	22	23
第五趟	9	12	15	18	22	23

18

22

12

15

23

9

Erste Reise

18

22

12

15

9

23

Zweite Fahrt

18 td>9

12

15

22

23 td>

Die dritte Reise

15

9

12

18

22

23

Die vierte Reise

12

9

15

18

22

23

Die fünfte Reise

9

12

15

18

23

Der Code lautet wie folgt:

<?php
        $arr1 = array(18,22,12,15,23,9);
        $n = count($arr1);
        for ($i=0; $i < $n-1; $i++) { 
            //找最大值
            $max = $arr1[0];
            $max_key = 0;
            for ($k=0; $k < $n - $i; $k++) { 
                if ($arr1[$k] > $max) {
                    $max = $arr1[$k];
                    $max_key = $k;
                }
            }
            //交换
            $temp = $arr1[$max_key];
            $arr1[$max_key] = $arr1[$n-1-$i];
            $arr1[$n-1-$i] = $temp;
        }

Zusammenfassungsregeln:

1 Um den Maximalwert (und Index) vom Anfang bis zum Ende zu finden und ihn auszutauschen, beträgt die Anzahl der Male $n-1, $n ist die Array-Länge

2. Was Sie in jeder Reise tun müssen, ist: a) den Maximalwert ermitteln (rechts) und den Maximalwert mit dem letzten Element dieser Reise austauschen; 3. Die Anzahl der Daten, um den Maximalwert in jedem Durchgang zu ermitteln, ist 1 weniger als im vorherigen Durchgang, von denen es im ersten Durchgang $n gab.

Das obige ist der detaillierte Inhalt vonDetaillierte Analyse des Auswahlsortierungsalgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!