Detaillierte Erläuterung von Beispielen für die Implementierung der Einfügungssortierung in Java

Dieser Artikel stellt hauptsächlich die Java-Datenstruktur und die Algorithmus-Einfügungssortierung vor und analysiert die Konzepte, Klassifizierungen, Prinzipien, Implementierungsmethoden und zugehörigen Vorsichtsmaßnahmen der Java-Einfügungssortierung in Form von Beispielen

Das Beispiel in diesem Artikel beschreibt die Einfügungsart der Java-Datenstruktur und des Algorithmus. Ich teile es Ihnen als Referenz mit:

Nachdem ich das Wissen über das Sortieren in der Datenstruktur geklärt habe, habe ich es aufgeschrieben, weil ich es mit mehr Menschen teilen möchte. Das Wichtigste ist, einfach ein Backup für zukünftige Referenzzwecke zu erstellen.

Sortieren

1. Konzept:

Sequenz mit n Datensätzen {R1, R2, .......,Rn} (hier beachten: 1,2,n sind die Sequenzen in der Tabelle unten, und die folgenden haben den gleichen Effekt), und die Sequenz der entsprechenden Schlüsselwörter ist {K1,K2,. ... .....,Kn}. Durch Sortieren muss eine Anordnung p1, p2, ... pn der aktuellen Indexfolge 1,2, ..., n gefunden werden, damit das entsprechende Schlüsselwort die folgende nicht abnehmende (nicht zunehmende) Beziehung erfüllt , das heißt: Kp1<=Kp2<=Kpn, wodurch eine Folge von Datensätzen geordnet nach Schlüsselwörtern erhalten wird: {Rp1, Rp2,.....,Rpn}.

2. Klassifizierung

Die Sortierung kann basierend auf dem Unterschied im von den Daten während der Sortierung belegten Speicher in zwei Kategorien unterteilt werden.

Interne Sortierung: Der gesamte Sortiervorgang wird vollständig im Speicher ausgeführt, wie folgt:

Einfügungssortierung (direkte Einfügungssortierung, Halbeinfügungssortierung, Hill-Sortierung). ; 🎜>Auswahlsortierung, Baumauswahlsortierung, Heapsortierung);

Zuweisungssortierung (Mehrschlüssel). Sequenztabellenimplementierung der Wortsortierung, der verketteten Basissortierung und der Basissortierung)); Die Sortierung erfordert die Verwendung externer Speichergeräte (Festplattensortierung, Bandsortierung).

3. Stabilität Angenommen, es gibt mehrere Datensätze mit demselben Schlüsselwort in der zu sortierenden Reihenfolge. Angenommen, Ki=Kj(1<=i<=n,1<=j<=n,i != j), wenn Ri vor Rj steht (d. h. i<=j) in der Reihenfolge vor dem Sortieren, erhalten wir nach dem Sortieren If Ri Wenn Rj immer noch in der Reihenfolge steht, gilt die verwendete Sortiermethode als stabil. Wenn sich hingegen die führende Beziehung desselben Schlüsselworts während des Sortiervorgangs ändert, ist die verwendete Sortiermethode instabil.

Einfügesortierung: Idee: Jedes Mal, wenn ein zu sortierender Datensatz entsprechend seiner Schlüsselgröße an der entsprechenden Position in der zuvor sortierten Unterdatei eingefügt wird, bis alle Datensätze vollständig eingefügt sind .

Direkte Einfügungssortierung:

Algorithmusidee: Angenommen, die zu sortierenden Datensätze sind im ArrayR gespeichert [1.. n] in. Zunächst bildet R[1] einen geordneten Bereich und der ungeordnete Bereich ist R[2..n]. Von i=2 bis i=n wird R[i] nacheinander in den aktuell geordneten Bereich R[1..i-1] eingefügt, um einen geordneten Bereich mit n Datensätzen zu generieren.

Der in Java implementierte Code lautet wie folgt:

Algorithmusanalyse:

Der beste Fall ist, dass die Aufzeichnung auf Der schlimmste Fall ist, dass die zu sortierenden Datensätze in umgekehrter Reihenfolge nach Schlüsselwörtern angeordnet sind.

Die zeitliche Komplexität beträgt O(N^2) und die Raumkomplexität ist O(1);Dieser Algorithmus ist ein stabiler Sortieralgorithmus: eignet sich besser für Situationen, in denen die Anzahl der zu sortierenden Datensätze gering und grundsätzlich in Ordnung ist.

Sortierung mit halber Einfügung:

Algorithmusidee: Die Leistung der halbierten Suche nach geordneten Tabellen ist besser als die der sequentiellen Suche.

package exp_sort;
public class DirectInsertSort {
  public static void DircstSort(int array[]) {
    int j;
    // 循环从第二个数开始，第一个数用做存放待插入的记录
    for (int i = 1; i < array.length; i++) {
      int temp = array[i];
      // 寻找插入位置
      for (j = i; j > 0 && temp < array[j - 1]; j--) {
        array[j] = array[j - 1];
      }
      // 将待插入记录插入到已经排序的序列中
      array[j] = temp;
    }
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    DircstSort(array);
  }
}

Der Algorithmus-Implementierungscode lautet wie folgt:

Algorithmusanalyse: ist ein stabiler Sortieralgorithmus, besser als der Algorithmus für direktes Einfügen Reduziert die Anzahl der Vergleiche zwischen Schlüsselwörtern erheblich, sodass schneller ist als der Sortieralgorithmus für direktes Einfügen
, aber die Anzahl der Datensatzbewegungen hat sich nicht geändert, sodass sich die zeitliche Komplexität von

nicht geändert hat Der Sortieralgorithmus für halbierte Einfügung ist immer noch O (n ^ 2). ist derselbe wie der Sortieralgorithmus für direkte Einfügung. Zusätzliches Leerzeichen O(1).

【Verwandte Empfehlungen】

package exp_sort;
public class BinaryInsertSort {
  public static void sort(int array[]) {
    int temp, low, mid, high;
    for (int i = 1; i < array.length; i++) {
      temp = array[i];
      low = 0;
      high = i -1;
      //确定插入位置
      while (low <= high) {
        mid = (low + high) / 2;
        if (temp < array[mid]) {
          high = mid - 1;
        } else {
          low = mid + 1;
        }
      }
      //记录依次向后移动
      for (int j = i; j >= low + 1; j--) {
        array[j] = array[j-1];
      }
      //插入记录
      array[low] = temp;
    }
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = {38, 62, 35, 77, 55, 14, 35, 98};
    sort(array);
  }
}

1.

Besondere Empfehlung: "php Download der Version „Programmer Toolbox“ V0.1

2. Kostenloses Java-Video-Tutorial

3. YMP Online-Handbuch

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung von Beispielen für die Implementierung der Einfügungssortierung in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!