Einfaches Beispiel für eine Java-Einfügungssortierung

In diesem Artikel werden hauptsächlich Java-Einfügesortierungsbeispiele im Detail vorgestellt, die einen bestimmten Referenzwert haben

Grundkonzepte

Das Der grundlegende Vorgang der Einfügungssortierung besteht darin, Daten in die sortierten geordneten Daten einzufügen, um neue geordnete Daten mit der Zahl plus eins zu erhalten. Der Algorithmus eignet sich zum Sortieren einer kleinen Datenmenge und der Zeit Die Komplexität ist O(n^2). Es handelt sich um eine stabile Sortiermethode. Der Einfügealgorithmus teilt das zu sortierende Array in zwei Teile: Der erste Teil enthält alle Elemente des Arrays mit Ausnahme des letzten Elements (wodurch das Array um einen weiteren Platz für eine Einfügeposition erweitert wird), und der zweite Teil enthält nur dieses Element (d. h. das einzufügende Element). Nachdem der erste Teil sortiert ist, wird dieses letzte Element in den sortierten ersten Teil eingefügt.

2. Java-Code-Implementierung

public class InsertSort {
  public static void inserSort(int[] array){
    if (array==null||array.length<2){
      return;
    }

    for (int i=1;i<array.length;i++){ //默认第一个元素为有序队列，从第二个元素开始循环插入
      int position=array[i];     //设置第二个元素为要插入的数据
      int j=i-1;
      while (j>=0&&position<array[j]){
        array[j+1]=array[j];   //如果插入发数小于第j个元素，将第j个数向后移
        j--;
      }
      array[j+1]=position;     //插入
    }
  }

  public static void main(String ags[]){
    int[] array={2,6,4,7,3,-1};
    inserSort(array);
    for (int i=0;i<array.length;i++){
      System.out.print(array[i]+" ");
    }
  }
}

3. Leistungsanalyse

Stabil
Raumkomplexität O(1)
Zeitkomplexität O(n2)
Worst Case: umgekehrte Reihenfolge, es müssen n*(n-1)/2 Elemente verschoben werden
Best Case Situation: Positiv Reihenfolge, Elemente müssen nicht verschoben werden

Das obige ist der detaillierte Inhalt vonEinfaches Beispiel für eine Java-Einfügungssortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!