1. Überblick:

　　

Dieser Artikel bietet die Prinzipien und Java-Implementierungen mehrerer gängiger Sortieralgorithmen, einschließlich gängiger einfacher Sortier- und fortgeschrittener Sortieralgorithmen sowie weiterer häufig verwendeter Algorithmuskenntnisse.

  • Einfache Sortierung: Bubble Sort, Selection Sort, Insertion Sort
  • Fortgeschrittene Sortierung: Quick Sort, Merge Sort, Shell Sort
  • Verwandtes Algorithmuswissen: Partitionierung, Rekursion, Binäre Suche

2. Bubble Sort:

(1) Prinzip:

  • 1. Beginne mit dem ersten Datenelement und vergleiche es mit dem zweiten Datenelement. Wenn das zweite Datenelement kleiner als das erste ist, tausche die Positionen der beiden Datenelemente.
  • 2. Der Zeiger bewegt sich vom ersten Datenelement zum zweiten Datenelement, und das zweite Datenelement wird mit dem dritten Datenelement verglichen. Wenn das dritte Datenelement kleiner als das zweite Datenelement ist, werden die Positionen der beiden Datenelemente getauscht.
  • 3. Und so weiter, womit die erste Sortierrunde abgeschlossen wird. Nach der ersten Runde wurde das größte Element ganz nach rechts verschoben.
  • 4. Führen Sie die zweite Sortierrunde gemäß dem obigen Ablauf durch und platzieren Sie das zweitgrößte Element an der vorletzten Position.
  • 5. Wiederholen Sie den obigen Vorgang. Jedes Mal, wenn eine Runde abgeschlossen ist, verringert sich die Anzahl der Vergleiche um eins.

(2) Beispiel:

Zu sortierende Daten: 7, 6, 9, 8, 5, 1

Ablauf der ersten Sortierrunde:

指针先指向7，7和6比较，6<7，交换6和7的位置，结果为：6,7,9,8,5,1
指针指向第二个元素7，7和9比较，9>7，不用交换位置，结果仍为：6,7,9,8,5,1
指针指向第三个元素9，比较9和8，8<9，交换8和9的位置，结果为：6,7,8,9,5,1
指针指向第四个元素9，比较9和5，5<9，交换5和9，结果为：6,7,8,5,9,1
指针指向第五个元素9，比较9和1，1<9，交换1和9的位置，结果为6,7,8,5,1,9

Nach der ersten Sortierrunde wird die größte Zahl, 9, ganz nach rechts verschoben.

Fahren Sie mit der zweiten Sortierrunde fort. Der Ablauf ist derselbe wie oben, außer dass die größte Zahl 9 bereits ganz rechts steht und 9 nicht erneut verglichen werden muss, wodurch ein Vergleich eingespart wird. Das Ergebnis nach der zweiten Runde ist: 6,7,5,1,8,9

Ergebnis der dritten Runde: 6,5,1,7,8,9

Vergleichsergebnis der vierten Runde: 5,1,6,7,8,9

Vergleichsergebnis der fünften Runde: 1,5,6,7,8,9

Das endgültige Sortierergebnis ist: 1,5,6,7,8,9. Aus dem Obigen ist ersichtlich, dass das Sortieren von N Datenelementen N-1 Sortierrunden erfordert; die Anzahl der im i-ten Durchgang benötigten Vergleiche ist N-i.

(3) Programmieransatz:

Es sind zwei Schleifenebenen erforderlich. Die erste Schleife, i, repräsentiert die Anzahl der Sortierrunden, und die zweite Schleife, j, repräsentiert die Anzahl der Vergleiche.

(4) Code-Implementierung:

Beispiel

package com.test.insertsort; /** * Auswahl-Sortierung * @author Administrator * */ public class ChooseSort { private int[] array; private int length; public ChooseSort(int[] array){ this.array = array; this.length = array.length; } /** * Alle Elemente im Array ausgeben **/ public void display(){ for(int i: array){ System.out.print(i+" "); } System.out.println(); } /** * Auswahl-Sortieralgorithmus **/ public void chooseSort(){ for(int i=0; i<length-1; i++){ int minIndex = i; for(int j=minIndex+1;j<length;j++){ if(array[j]<array[minIndex]){ minIndex = j; } } int temp = array[i]; array[i] = array[minIndex]; array[minIndex] = temp; } } public static void main(String[] args){ int[] array={100,45,36,21,17,13,7}; ChooseSort cs = new ChooseSort(array); System.out.println("Daten vor dem Sortieren:"); cs.display(); cs.chooseSort(); System.out.println("Daten nach dem Sortieren:"); cs.display(); } }

(5) Zusammenfassung zur Auswahlsortierung:

N Elemente erfordern N-1 Sortierdurchläufe;

Die i-te Runde erfordert N-i Vergleiche;

Das Sortieren von N Elementen erfordert n(n-1)/2 Vergleiche;

Die algorithmische Komplexität der Auswahlsortierung ist weiterhin O(n*n);

Im Vergleich zu Bubblesort ist die Anzahl der Vertauschungen bei der Auswahlsortierung stark reduziert, daher ist sie schneller als Bubblesort.

4. Insertionssortierung

Die Insertionssortierung ist der schnellste Sortieralgorithmus unter den einfachen Sortierverfahren. Obwohl ihre Zeitkomplexität weiterhin O(n*n) beträgt, ist sie viel schneller als Bubblesort und Auswahlsortierung.

(1) Prinzip:

  • 1. Richte den Zeiger auf ein Element. Nimm an, dass alle Elemente links davon geordnet sind. Entnimm dieses Element und vergleiche es dann von rechts nach links mit den Elementen links davon. Wenn ein Element gefunden wird, das größer als es ist, verschiebe dieses Element nach rechts. Stoppe, wenn ein Element gefunden wird, das kleiner als es ist, oder wenn du ganz links angekommen bist und feststellst, dass alle Elemente links davon größer als es sind.
  • 2. An diesem Punkt erscheint eine leere Position. Setze das Element in diese leere Position. Jetzt sind alle Elemente links von diesem Element kleiner als es, und alle Elemente rechts davon sind größer als es.
  • 3. Bewege den Zeiger eine Position zurück und wiederhole den obigen Vorgang. Nach jeder Runde der Operation erhöht sich die Anzahl der geordneten Elemente links um eins, und die Anzahl der ungeordneten Elemente rechts verringert sich um eins.

(2) Beispiel:

Zu vergleichende Daten: 7, 6, 9, 8, 5, 1

  • Erste Runde: Der Zeiger zeigt auf das zweite Element, 6. Angenommen, die Elemente links von 6 sind sortiert. Entnehme 6, wodurch 7,_,9,8,5,1 entsteht. Beginne bei 7, vergleiche 6 mit 7 und stelle fest, dass 7>6 gilt. Verschiebe 7 nach rechts, wodurch _,7,9,8,5,1 entsteht. Füge 6 an der leeren Position vor 7 ein. Ergebnis: 6,7,9,8,5,1
  • Zweite Runde: Der Zeiger zeigt auf das dritte Element, 9. Zu diesem Zeitpunkt sind die Elemente links davon, 6,7, sortiert. Entnehme 9, wodurch 6,7,_,8,5,1 entsteht. Beginne bei 7, vergleiche jedes Element nacheinander mit 9, und stelle fest, dass alle Elemente links von 9 kleiner als 9 sind, daher ist keine Verschiebung nötig. Setze 9 in die leere Position ein. Das Ergebnis ist weiterhin: 6,7,9,8,5,1
  • Dritte Runde: Der Zeiger zeigt auf das vierte Element, 8. Zu diesem Zeitpunkt sind die Elemente links davon, 6,7,9, sortiert. Entnehme 8, wodurch 6,7,9,_,5,1 entsteht. Beginne bei 9, vergleiche jedes Element nacheinander mit 8, und stelle fest, dass 8<9 gilt. Verschiebe 9 nach rechts, wodurch 6,7,_,9,5,1 entsteht. Füge 8 an der leeren Position ein. Ergebnis: 6,7,8,9,5,1
  • Vierte Runde: Der Zeiger zeigt auf das fünfte Element, 5. Zu diesem Zeitpunkt sind die Elemente links davon, 6,7,8,9, sortiert. Entnehme 5, wodurch 6,7,8,9,_,1 entsteht. Beginne bei 9, vergleiche jedes Element nacheinander mit 5, und stelle fest, dass 5 kleiner als alle Elemente links davon ist. Alle Elemente links von 5 werden nach rechts verschoben, wodurch _,6,7,8,9,1 entsteht. Setze 5 in die leere Position ein. Ergebnis: 5,6,7,8,9,1.
  • Fünfte Runde: Wie oben. 1 wird ganz nach links verschoben. Endergebnis: 1,5,6,7,8,9.

(3) Codeanalyse:

Es werden zwei Schleifenebenen benötigt. Die erste Schleife, index, repräsentiert den Zeiger im obigen Beispiel, das heißt, sie durchläuft jedes Element beginnend bei Koordinate 1. Die zweite Schleife beginnt bei leftindex=index-1 und läuft mit leftindex-- nach links, wobei jedes Element mit dem Element bei i verglichen wird, bis das Element bei j kleiner als das Element bei i ist oder leftindex<0. Durchlaufe jedes Element von i bis j, um es nach rechts zu verschieben, und setze schließlich das Element bei index in die leere Position bei leftindex ein.

(4) Code-Implementierung:

Beispiel

package com.test.insertsort; /** * Einfügesortieralgorithmus: * 1. Verwenden Sie eine bestimmte Position im Array als Trennposition, z. B. index=1, und nehmen Sie an, dass die linke Seite vollständig sortiert ist. * * 2. Entnehmen Sie die Daten an der Position index und legen Sie sie in eine temporäre Variable. Jetzt ist die Position index leer. * * 3. Beginnen Sie bei leftindex=index-1 und vergleichen Sie die Daten links mit den Daten am aktuellen Index (d. h. temp). Wenn array[leftindex]>temp, * dann verschieben Sie array[leftindex] um eine Position nach hinten, d. h. array[leftindex+1]=array[leftindex]. Zu diesem Zeitpunkt wird leftindex leer. * * 4. Vergleichen Sie dann die Daten bei index-2 (d. h. leftindex=leftindex-1) mit temp, wiederholen Sie Schritt 3, * bis Daten gefunden werden, die <=temp sind, oder bis zum ganz linken Rand verglichen wurde (was bedeutet, dass temp der kleinste ist); hören Sie mit dem Vergleichen auf und platzieren Sie temp an der aktuellen leeren Position. * * 5. Verschieben Sie index um 1 nach hinten, d. h. index=index+1, temp=array[index], wiederholen Sie die Schritte 2-4, bis index=array.length, die Sortierung endet, * und die Daten im Array sind nun in aufsteigender Reihenfolge. * * @author bjh * */ public class InsertSort { private int[] array; private int length; public InsertSort(int[] array){ this.array = array; this.length = array.length; } public void display(){ for(int a: array){ System.out.print(a+" "); } System.out.println(); } /** * Methode zur Einfügesortierung **/ public void doInsertSort(){ for(int index = 1; index<length; index++){//Der äußere Index bewegt sich nach rechts, d. h. der Index der Daten, die als Vergleichsobjekt verwendet werden. int temp = array[index];//Die zum Vergleich verwendeten Daten. int leftindex = index-1; while(leftindex>=0 && array[leftindex]>temp){//Wenn der Vergleich ganz links ankommt oder auf Daten stößt, die kleiner als temp sind, beende die Schleife. array[leftindex+1] = array[leftindex]; leftindex--; } array[leftindex+1] = temp;//Setze temp in die leere Position. } } public static void main(String[] args){ int[] array = {38,65,97,76,13,27,49}; InsertSort is = new InsertSort(array); System.out.println("Daten vor dem Sortieren:"); is.display(); is.doInsertSort(); System.out.println("Daten nach dem Sortieren:"); is.display(); } }

(5) Analyse der Insertionssortierung:

Zeitkomplexität: Da weiterhin zwei Schleifenebenen benötigt werden, ist die Zeitkomplexität der Insertionssortierung weiterhin O(n*n).

Anzahl der Vergleiche: In der ersten Sortierrunde vergleicht die Insertionssortierung höchstens einmal; in der zweiten Runde höchstens zweimal; und so weiter. In der letzten Runde vergleicht sie höchstens N-1 Mal. Daher ist die maximale Anzahl der Vergleiche für die Insertionssortierung 1+2+...+N-1=N*(N-1)/2. Dennoch führt die Insertionssortierung tatsächlich nur selten so viele Vergleiche durch, denn sobald links ein Element gefunden wird, das kleiner als das Zielelement ist, stoppt der Vergleich. Daher ist die durchschnittliche Anzahl der Vergleiche für die Insertionssortierung N*(N-1)/4.

Anzahl der Verschiebungen: Die Anzahl der Verschiebungen bei der Insertionssortierung ist fast genauso hoch wie die Anzahl der Vergleiche, aber das Verschieben ist viel schneller als das Tauschen.

Zusammenfassend ist Insertionsort etwa doppelt so schnell wie Bubblesort (halbe Anzahl an Vergleichen) und etwas schneller als Selectionsort. Bei nahezu sortierten Daten ist Insertionsort sehr schnell, was es zum effizientesten Sortieralgorithmus unter den einfachen Sortierverfahren macht.

Quicksort, Bubblesort, Selectionsort, Insertionsort, Mergesort

1. Überblick:

Der vorherige Artikel stellte gängige einfache Algorithmen vor: Bubblesort, Selectionsort und Insertionsort. Dieser Artikel stellt fortgeschrittene Sortieralgorithmen vor: Quicksort und Mergesort. Bevor wir die Algorithmen vorstellen, führen wir zunächst das für fortgeschrittene Algorithmen erforderliche Grundwissen ein: Partitionierung und Rekursion, und behandeln außerdem den binären Suchalgorithmus.

2. Partitionierung:

Die Partitionierung ist die Voraussetzung für Quicksort, das heißt, die Daten in zwei Gruppen aufzuteilen: Daten, die größer als ein bestimmter Wert sind, in eine Gruppe und Daten, die kleiner als ein bestimmter Wert sind, in die andere Gruppe. Quicksort wird durch Partitionierung und rekursive Operationen umgesetzt.

(1) Prinzip:

Definiere einen Schwellenwert. Durchlaufe Elemente vom äußersten linken und rechten Rand zur Mitte. Halte an, wenn du links Daten findest, die größer als der Schwellenwert sind, und halte an, wenn du rechts Daten findest, die kleiner als der Schwellenwert sind. Wenn die linke und rechte Seite die Mitte noch nicht erreicht haben, tausche die Daten, die links größer als der Schwellenwert sind, mit den Daten, die rechts kleiner als der Schwellenwert sind. Wiederhole den obigen Vorgang, bis sich der linke und der rechte Zeiger treffen. An diesem Punkt sind alle Daten auf der linken Seite kleiner als der Schwellenwert und alle Daten auf der rechten Seite größer als der Schwellenwert, und die Partition endet. Nach der Partitionierung sind die Daten noch ungeordnet, aber näher an einer geordneten Reihenfolge.

(2) Beispiel:

Zu partitionierende Daten: 7, 6, 9, 8, 5, 1, wobei angenommen wird, dass der Schwellenwert 5 ist

Erste Runde: Der linke Zeiger zeigt auf 7, der rechte Zeiger zeigt auf 1. Der linke Zeiger bewegt sich rückwärts, und der rechte Zeiger bewegt sich nach links. Es wird festgestellt, dass das erste Element größer als 5 auf der linken Seite 7 ist und das erste Element kleiner als 5 auf der rechten Seite 1 ist. Tausche 7 und 1. Ergebnis: 1, 6, 9, 8, 5, 7;

Zweite Runde: Ausgehend von 6 wird eine Zahl größer als 5 gesucht, und es wird 6 gefunden. Auf der rechten Seite wird ausgehend von 5 eine Zahl kleiner als 5 gesucht, und es wird 1 gefunden. Da sich 6 nun rechts von 1 befindet, das heißt, rechter Zeiger < linker Zeiger, kreuzen sich der linke und der rechte Zeiger, und die Partition endet. Die ursprüngliche Sequenz wird in zwei Teile geteilt. Die linke Teilsequenz hat nur ein Element, 1, welches die Teilsequenz kleiner als der Schwellenwert ist; die rechte Teilsequenz enthält 5 Elemente, alle größer als der Schwellenwert 5.

(3) Code-Implementierung:

Beispiel

package com.test.insertsort; /** * Partition, Rekursion, Quicksort * @author bjh * */ public class QuickSort { /** Zu sortierendes/partitionierendes Array*/ private int[] array; /** Array-Länge*/ private int length; public QuickSort(int[] array){ this.array = array; this.length = array.length; } /** * Element ausgeben*/ public void printArray(){ for(int i=0; i<length; i++){ System.out.print(array[i]+" "); } System.out.println(); } /** * Partition @return Der Partitionsgrenzpunkt*/ public int partition(int left, int right, int pivot){ //Der Startpunkt des linken Zeigers. left-1 ist, weil in der nachfolgenden Schleife bei jedem Durchlauf der linke Zeiger nach rechts bewegt wird. //Dies stellt sicher, dass der linke Zeiger vom ersten Element links startet; andernfalls würde er vom zweiten starten. int leftpoint = left-1; //Der Startpunkt des rechten Zeigers. right+1 ist, weil in der nachfolgenden Schleife bei jedem Durchlauf der rechte Zeiger nach links bewegt wird. //Dies stellt sicher, dass der rechte Zeiger von ganz rechts startet; andernfalls würde er vom vorletzten starten. int rightpoint = right+1; while(true){ //Finde Daten auf der linken Seite, die größer als pivot sind, oder wenn es das rechte Ende erreicht, ohne Daten größer als pivot zu finden. while(leftpoint<right && array[++leftpoint]<pivot); //Finde Daten auf der rechten Seite, die kleiner als pivot sind, oder wenn es das linke Ende erreicht, ohne Daten kleiner als pivot zu finden. while(rightpoint>left && array[--rightpoint]>pivot); //Der linke Zeiger und der rechte Zeiger überlappen oder schneiden sich. if(leftpoint >= rightpoint){ break; }else{ //Tausche die größeren Daten links mit den kleineren Daten rechts. swap(leftpoint,rightpoint); } } //Gibt den Grenzpunkt zurück, d. h. den am weitesten links liegenden Punkt im rechten Teilarray. return leftpoint; } /** * Daten tauschen*/ public void swap(int leftpoint,int rightpoint){ int temp = array[leftpoint]; array[leftpoint] = array[rightpoint]; array[rightpoint] = temp; } public static void main(String args[]){ int[] array = {99,78,26,17,82,36,9,81,22,100,30,20,17,85}; QuickSort qs = new QuickSort(array); System.out.println("Die Daten vor der Partitionierung sind:"); qs.printArray(); int bound = qs.partition(0, array.length-1, 50); System.out.println("Die Daten nach der Partitionierung sind:"); qs.printArray(); System.out.println("Der Grenzpunkt der Partition ist:" + array[bound] + ", die Koordinate des Grenzpunkts ist:" + Schranke); } }

Das Ergebnis der Ausführung ist:

Original-Link: https://www.cnblogs.com/bjh1117/p/8335628.html