Java-Datenstruktur-Sortieralgorithmus (3) einfache Auswahlsortierung

In diesem Artikel wird hauptsächlich die Einfachheit von Java-Datenstrukturen und -Algorithmen Auswahlsortierung vorgestellt und die Prinzipien, Implementierungsmethoden und zugehörigen Betriebstechniken der Auswahlsortierung anhand von Beispielen analysiert it

Die Beispiele in diesem Artikel beschreiben die einfache Auswahlsortierung von Java-Datenstrukturen und -Algorithmen. Ich teile es Ihnen als Referenz mit:

Im vorherigen Artikel haben wir bereits den Sortieralgorithmus der Austauschklasse beschrieben. In diesem Abschnitt werden wir mit der Sortierung beginnen Schauen wir uns zunächst den Auswahlsortierungsalgorithmus an:

Grundlegende algorithmische Idee der Auswahlsortierung >Jede Fahrt ist in n-i+1 (i=1,2, Wählen Sie den Datensatz mit dem kleinsten Schlüsselwort unter 3,...,n-1) Datensätzen als i-ter Datensatz in der geordneten Reihenfolge.

Einfache Auswahlsortierung:

Angenommen, die Anzahl der Datensätze in der sortierten Reihenfolge beträgt n. Ich nehme 1,2,…,n-1, finde den Datensatz mit dem kleinsten Sortiercode aus allen n-i+1 Datensätzen (Ri, Ri+1,…,Rn) und tausche ihn mit dem i-ten Datensatz aus. Nach n-1-maliger Ausführung ist die Sortierung der Datensatzsequenz abgeschlossen.

Der Algorithmus-Implementierungscode lautet wie folgt:

package exp_sort;
public class SimpleSelectSort {
  static int i;
  static int temp;
  public static void selectSort(int array[]) {
    for (i = 0; i < array.length; i++) {
      int k = i;  //记录当前位置
      for (int j = i + 1; j < array.length; j++) {
        if (array[j] < array[k]) {   //找出最小的数，并用k指向最小数的位置
          k = j;
        }
      }
            //交换最小数array[k]与第i位上的数
      if (k != i) {
        temp = array[i];
        array[i] = array[k];
        array[k] = temp;
      }
    }
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    selectSort(array);
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
}

Algorithmusanalyse:

Während dieses Sortiervorgangs wird aufgezeichnet müssen verschoben werden. Die Häufigkeit ist relativ gering. Im besten Fall ist der Ausgangszustand der zu sortierenden Datensätze bereits in positiver Reihenfolge, im schlimmsten Fall besteht keine Notwendigkeit, die Datensätze zu verschieben In umgekehrter Reihenfolge beträgt die maximale Anzahl erforderlicher Züge: 3 (n-1). Die Anzahl der beim Sortiervorgang 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 = n, beträgt die Gesamtzahl der erforderlichen Vergleiche: n (n-1) / 2, dh die zeitliche Komplexität der Vergleichsoperation beträgt: O( n^ 2), die zeitliche Komplexität des Verschiebevorgangs beträgt O(n); diese Sortierung ist

instabile Sortierung

. [Verwandte Empfehlungen]

1. Java-Datenstruktur-Sortieralgorithmus (1) Baumauswahlsortierung

2 Algorithmus (2) Zusammenführungssortierung

3.

Detailliertes Tutorial zur Auswahlsortierung (Selection Sort_java) in Java

4.

Java-Datenstruktur-Sortieralgorithmus (4) Auswahlsortierung

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