Beispiel für eine Java-Direkteinfügungssortierung

Die Faktoren, die die Sortiereffizienz beeinflussen, werden im Allgemeinen unter drei Aspekten verglichen: der Anzahl der Datenvergleiche, der Anzahl der Datenverschiebungen und der Menge des belegten Speicherplatzes.
Lassen Sie uns einen allgemeinen Vergleich zwischen Blasensortierung, Auswahlsortierung, Einfügungssortierung und Schnellsortierung durchführen. Der Blasensortierungsalgorithmus wird im Allgemeinen nicht verwendet, da er unter mehreren Sortieralgorithmen die größte Anzahl an Vergleichen und Verschiebungen aufweist. Sein einziger Vorteil besteht darin, dass der Algorithmus einfach und leicht zu verstehen ist und daher verwendet werden kann, wenn die Datenmenge gering ist wird ein gewisser Anwendungswert sein. Die Auswahlsortierung hat die gleiche Anzahl an Vergleichen wie die Blasensortierung, die n im Quadrat ist, aber sie reduziert die Anzahl der Austausche auf ein Minimum, sodass sie angewendet werden kann, wenn die Datenmenge klein ist und der Datenaustausch zeitaufwändiger ist als der Vergleich Daten auswählen.
In den meisten Fällen ist der Einfügungssortierungsalgorithmus die beste Wahl, wenn die Datenmenge relativ klein oder grundsätzlich geordnet ist. Zum Sortieren größerer Datenmengen ist Quicksort normalerweise die beste Methode.
Der obige Sortieralgorithmus benötigt sehr wenig Speicherplatz und erfordert lediglich eine zusätzliche Variable, um die Datenelemente während des Austauschs vorübergehend zu speichern. Daher gibt es keinen Vergleich hinsichtlich der Größe des belegten Speicherplatzes.

Die Anzahl der Vergleiche der Einfügungssortierung beträgt immer noch n im Quadrat, aber im Allgemeinen ist sie doppelt so schnell wie die Blasensortierung und etwas schneller als die Auswahlsortierung. Es wird häufig in der Endphase komplexer Sortieralgorithmen wie Quicksort verwendet.

Algorithmus: Nach der i-1-Verarbeitung wurde L[1..i-1] sortiert. Der i-te Verarbeitungsdurchgang fügt L[i] nur an der entsprechenden Position von L[1..i-1] ein,
wodurch L[1..i] wieder zu einer sortierten Sequenz wird. Um dieses Ziel zu erreichen, können wir einen sequentiellen Vergleich verwenden.
Vergleichen Sie zuerst L[i] und L[i-1]. Wenn L[i-1] Andernfalls tauschen Sie die Positionen von L[i] und L[i-1] aus und vergleichen Sie L[i-1] und L[i-2] bis zu einer bestimmten Position j (1≤j≤i -1),
bis L[j] ≤ L[j+1]
Vorteile: weniger bewegliche Elemente, nur ein Hilfsraum wird benötigt
Zeitkomplexität n*n
Beim Warten Dies ist eine gute Sortiermethode, wenn die Anzahl der sortierten Datensätze n klein ist. Aber wenn n sehr groß ist, ist es ungeeignet

Zum Beispiel: int[] Values ​​​​= { 5, 2, 4, 1, 3 }

Sortiervorgang:
1. Mal: ​​2 ,5,4,1,3
Das 2. Mal: ​​2,4,5,1,3
Das 3. Mal: ​​1,2,4,5,3
Das 4. Mal : 1,2 ,3,4,5

Java-Code:

public class InsertSort {
   public static void main(String[] args) {
       int[] values = { 5, 2, 4, 1, 3 };
       sort(values);
       for (int i = 0; i < values.length; ++i) {
           System.out.println(values[i]);
       }
   }
   public static void sort(int[] values) {
       int temp;
       int j = 0;
       for (int i = 1; i < values.length; i++) {
           if(values[i]<values[i-1])//此处的判断很重要，这里体现了插入排序比冒泡排序和选择排序快的原因。
           {
               temp = values[i];
               //数据往后移动
               for (j=i-1; j>=0 && temp<values[j]; j--)
               {
                   values[j+1] =values[j];
               }
               //将数据插入到j+1位置
               values[j+1] =temp;
               System.out.print("第" + (i + 1) + "次：");
               for (int k = 0; k < values.length; k++) {
                   System.out.print(values[k]+",");
               }
               System.out.println("");
           }
       }
   }
}

Zweites Beispiel

package cn.cqu.coce.xutao;
public class zhijiecharu {

 public static void main(String args[]){

 int a[]={1,2,34,67,8,9,6,7,56,34,232,99};
 int i,j,k;
 for(i=0;i<a.length;i++)
  System.out.print(a[i]+"\t");
 System.out.println();
 for(i=1;i<a.length;i++){

  for(j=i-1;j>=0;j--)
   if(a[i]>a[j])
    break;

  if(j!=i-1){
   int temp;
   temp=a[i];
   for(k=i-1;k>j;k--)
    a[k+1]=a[k];
   a[k+1]=temp;  
  }  
 }
 for(i=0;i<a.length;i++)
  System.out.print(a[i]+"\t");
 System.out.println();
  }
}

Weitere Beispiele für die Sortierung von Java-Direkteinfügungen und verwandte Artikel finden Sie auf der chinesischen PHP-Website!