Stabilität (Stabilität)
Ein Sortieralgorithmus ist stabil, das heißt, wenn es zwei gleiche Datensätze mit den Schlüsseln R und S gibt und R in der Originalliste vor S erscheint, erscheint R auch vor S in der sortierten Liste.
Klassifizierung des Sortieralgorithmus
Zu den häufigsten gehören Einfügen (Einfügungssortierung/Hill-Sortierung), Austausch (Blasensortierung/Schnellsortierung), Auswahl (Auswahlsortierung), Zusammenführung (Zusammenführungssortierung) usw.
1. Einfügungssortierung
Die Einfügungssortierung (Insertion Sort) funktioniert durch die Erstellung einer geordneten Sequenz. Bei unsortierten Daten wird die sortierte Sequenz von hinten nach vorne durchsucht, um die entsprechende Position zu finden und einzufügen. Bei der Implementierung der Einfügungssortierung wird normalerweise die In-Place-Sortierung verwendet (d. h. eine Sortierung, die nur O(1) zusätzlichen Platz beansprucht). Daher ist es während des Scanvorgangs erforderlich, die Sortierung wiederholt und schrittweise zu verschieben Sortiert Elemente rückwärts und bietet Platz für das Einfügen des neuesten Elements.
Im Allgemeinen wird die Einfügungssortierung für Arrays mithilfe von In-Place implementiert. Der spezifische Algorithmus wird wie folgt beschrieben:
Ab dem ersten Element können die Elemente als sortiert betrachtet werden.
Holen Sie sich das nächste Element und scannen Sie es von hinten nach vorne in der sortierten Reihenfolge der Elemente.
Wenn das Element (sortiert) größer als das neue Element ist, verschieben Sie das Element an die nächste Position.
Wiederholen Sie Schritt 3, bis Sie eine Position finden, an der das sortierte Element kleiner oder gleich dem neuen Element ist.
Nach dem Einfügen des neuen Elements an dieser Position.
Wiederholen Sie die Schritte 2 bis 5.
Kopieren Sie den Codecode wie folgt:
public static void insertSort(int[] data) {
for (int index = 1; index < data.length; index++) {
int key = data[index];
int Position = Index;
// größere Werte nach rechts verschieben
while (position > 0 && data[position - 1] > key) {
Daten[Position] = Daten[Position - 1];
Position--;
}
data[position] = key;
}
}
2. Hügelsortierung
Shell Sort ist eine Art Einfügungssortierung. Es handelt sich um eine Verbesserung gegenüber dem Sortieralgorithmus mit direkter Einfügung. Diese Methode wird auch als reduzierende inkrementelle Sortierung bezeichnet, da DL. Shell wurde nach seinem Vorschlag im Jahr 1959 benannt.
Die Hill-Sortierung schlägt eine verbesserte Methode vor, die auf den folgenden zwei Eigenschaften der Einfügungssortierung basiert:
Die Einfügungssortierung ist hocheffizient, wenn sie mit fast sortierten Daten arbeitet, dh sie kann die Effizienz der linearen Sortierung erreichen.
Die Einfügungssortierung ist jedoch im Allgemeinen ineffizient, da die Einfügungssortierung Daten jeweils nur um ein Bit verschieben kann.
Kopieren Sie den Codecode wie folgt:
static <E erweitert Comparable<? super E>> void shellSort(List<E> a) {
int h = 1;
while (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) von Knuth,1973>: 1, 4, 13, 40, 121, . ..
für (; h >= 1; h /= 3)
for (int i = h; i < a.size(); i++)
for (int j = i; j >= h && a.get(j).compareTo(a.get(jh)) < 0; j-=h)
Collections.swap(a, j, jh);
}
3. Blasensortierung
Bubble Sort (Bubble Sort, aus Taiwan übersetzt als: Bubble Sort oder Bubble Sort) ist ein einfacher Sortieralgorithmus. Es durchläuft wiederholt die zu sortierende Sequenz, vergleicht jeweils zwei Elemente und vertauscht sie, wenn sie in der falschen Reihenfolge sind. Der Besuch des Arrays wird wiederholt, bis kein Austausch mehr erforderlich ist, was bedeutet, dass das Array sortiert wurde. Der Name dieses Algorithmus rührt von der Tatsache her, dass kleinere Elemente durch den Austausch langsam an die Spitze des Arrays „schweben“.
Der Blasensortierungsalgorithmus funktioniert wie folgt:
Vergleichen Sie benachbarte Elemente und tauschen Sie beide aus, wenn das erste größer als das zweite ist.
Machen Sie dasselbe für jedes Paar benachbarter Elemente, beginnend mit dem ersten Paar und endend mit dem letzten Paar. An diesem Punkt sollte das letzte Element die größte Zahl sein.
Wiederholen Sie die obigen Schritte für alle Elemente außer dem letzten.
Wiederholen Sie die obigen Schritte jedes Mal für immer weniger Elemente, bis keine Zahlenpaare mehr zum Vergleichen übrig sind.
Kopieren Sie den Codecode wie folgt:
public static void bubbleSort(int[] data) {
int temp = 0;
for (int i = data.length - 1; i > 0; --i) {
boolean isSort = false;
for (int j = 0; j < i; ++j) {
if (data[j + 1] < data[j]) {
temp = data[j];
Daten[j] = Daten[j + 1];
data[j + 1] = temp;
isSort = true;
}
}
// Wenn in einer inneren Schleife ein Austausch stattfindet, wird der Vergleich fortgesetzt. Wenn in einer inneren Schleife kein Austausch stattfindet, wird davon ausgegangen, dass er sortiert wurde.
if (!isSort)
brechen;
}
}
4. Schnelle Sortierung
Quicksort ist eine Verbesserung der Blasensortierung. 1962 von CAR Hoare vorgeschlagen. Seine Grundidee besteht darin, die zu sortierenden Daten durch eine Sortierung in zwei unabhängige Teile aufzuteilen. Alle Daten in einem Teil sind kleiner als alle Daten im anderen Teil und dann wird diese Methode verwendet, um die beiden Teile der Daten schnell zu trennen Beim Sortieren kann der gesamte Sortiervorgang rekursiv durchgeführt werden, sodass die gesamten Daten zu einer geordneten Sequenz werden.
Bei der Schnellsortierung wird die Divide-and-Conquer-Strategie verwendet, um eine Liste in zwei Unterlisten zu unterteilen.
Die Schritte sind:
Das Auswählen eines Elements aus der Sequenz wird als „Pivot“ bezeichnet.
Ordnen Sie das Array neu an, sodass alle Elemente, die kleiner als der Basiswert sind, vor der Basis platziert werden und alle Elemente, die größer als der Basiswert sind, hinter der Basis platziert werden (die gleiche Anzahl kann auf beiden Seiten platziert werden). Nachdem diese Partition beendet wurde, befindet sich die Basis in der Mitte der Sequenz. Dies wird als Partitionsvorgang bezeichnet.
Sortieren Sie das Subarray der Elemente, die kleiner als der Basiswert sind, und das Subarray der Elemente, die größer als der Basiswert sind, rekursiv.
Kopieren Sie den Codecode wie folgt:
/*
* Effizientere Geräte für Quicksort
* Verwenden Sie den linken, mittleren und rechten Medianwert (@siehe #median()) für den Pivot und
* die effizientere innere Schleife für den Kern des Algorithmus.
*/
öffentliche Klasse Quicksort {
öffentliches statisches final int CUTOFF = 11;
/**
* Schnellsortieralgorithmus
*
* @param arr ein Array vergleichbarer Elemente
*/
public static <T erweitert Comparable<? super T>> void quicksort(T[] arr) {
quickSort(arr, 0, arr.length - 1);
}
/**
* Ermitteln Sie den Median von links, Mitte und rechts
* Ordnen Sie diese an und verbergen Sie den Pivot, indem Sie ihn am Ende des Arrays platzieren
*
* @param arr ein Array vergleichbarer Elemente
* @param hat den am weitesten links stehenden Index des Subarrays verlassen
* @param right der ganz rechte Index des Subarrays.<br />
* @return T
*/
public static <T erweitert Vergleichbares<? super T>> T median(T[] arr, int left, int right) {
int center = (links + rechts) / 2;
if (arr[left].compareTo(arr[center]) > 0)
swapRef(arr, left, center);
if (arr[left].compareTo(arr[right]) > 0)
swapRef(arr, left, right);
if (arr[center].compareTo(arr[right]) > 0)
swapRef(arr, center, right);
swapRef(arr, center, right - 1);
return arr[right - 1];
}
/**
* interne Methode zum Sortieren des Arrays mit dem Schnellsortierungsalgorithmus
*
* @param arr ein Array vergleichbarer Elemente
* @param hat den Index ganz links des Subarrays verlassen
* @param right der Index ganz rechts des Subarrays
*/
private static <T erweitert Comparable<? super T>> void quickSort(T[] arr, int left, int right) {
if (left + CUTOFF <= right) {
// finde den Drehpunkt
T Pivot = Median(arr, links, rechts);
// Partitionierung starten
int i = links, j = rechts - 1;
für (;;) {
while (arr[++i].compareTo(pivot) < 0);
while (arr[--j].compareTo(pivot) > 0);
wenn (i < j)
swapRef(arr, i, j);
anders
brechen;
}
// Tauschen Sie die Pivot-Referenz zurück auf die kleine Sammlung.
swapRef(arr, i, right - 1);
quickSort(arr, left, i - 1); // die kleine Sammlung sortieren.
quickSort(arr, i + 1, right); // die große Sammlung sortieren.
} anders {
// Wenn die Gesamtzahl kleiner als CUTOFF ist, verwenden wir die Einfügungssortierung
// stattdessen (weil es viel effizienter ist).
Sort(arr, Einfügung links, rechts);
}
}
/**
* Methode zum Austauschen von Referenzen in einem Array.<br />
*
* @param arr ein Array von Objekten
* @param idx1 der Index des ersten Elements
* @param idx2 der Index des zweiten Elements
*/
public static <T> void swapRef(T[] arr, int idx1, int idx2) {
T tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
/**
* Methode zum Sortieren eines Subarrays von Anfang bis Ende mit Einfügungssortierung
* Algorithmus. <br />
*
* @param arr ein Array vergleichbarer Elemente
* @param startet die Anfangsposition
* @param beendet die Endposition
*/
public static <T erweitert Comparable<? super T>> void insertSort(T[] arr, int start, int end) {
int i;
for (int j = start + 1; j <= end; j++) {
T tmp = arr[j];
for (i = j; i > start && tmp.compareTo(arr[i - 1]) < 0; i--) {
arr[i] = arr[i - 1];
}
arr[i] = tmp;
}
}
private static void printArray(Integer[] c) {
for (int i = 0; i < c.length; i++)
System.out.print(c[i] + ",");
System.out.println();
}
public static void main(String[] args) {
Integer[] data = {10, 4, 9, 23, 1, 45, 27, 5, 2};
System.out.println("bubbleSort...");
printArray(Daten);
Quicksort(Daten);
printArray(Daten);
}
}
5. Auswahlsortierung
Selection Sort ist ein einfacher und intuitiver Sortieralgorithmus. So funktioniert es. Suchen Sie zunächst das kleinste (große) Element in der unsortierten Sequenz und speichern Sie es am Anfang der sortierten Sequenz. Suchen Sie dann weiterhin das kleinste (große) Element aus den verbleibenden unsortierten Elementen und fügen Sie es dann am Ende ein sortierte Reihenfolge. Und so weiter, bis alle Elemente sortiert sind.
Da jeder Prozess zum Bestimmen von Elementen einen Unterprozess zum Auswählen des Mindestwerts hat, wird dies im Volksmund auch als Auswahlsortierung bezeichnet.
In der Sequenz 5 8 5 2 9 wissen wir beispielsweise, dass das erste Element 5 im ersten Durchgang durch 2 ausgetauscht wird. Dann wird die relative Reihenfolge der beiden 5er in der ursprünglichen Sequenz zerstört, sodass die Auswahlsortierung erfolgt nicht stabil. Sortieralgorithmus.
Kopieren Sie den Codecode wie folgt:
public static void selectSort(int[] data) {
int minIndex = 0;
int temp = 0;
for (int i = 0; i < data.length; i++) {
minIndex = i; //Der minimale Datenarray-Index des ungeordneten Bereichs
for (int j = i + 1; j < data.length; j++) { // Finden Sie die kleinsten Daten im ungeordneten Bereich und speichern Sie ihren Array-Index
if (data[j] < data[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) { // Wenn die minimale Position des ungeordneten Bereichs nicht die standardmäßigen ersten Daten sind, tauschen Sie sie aus.
temp = data[i];
data[i] = data[minIndex];
data[minIndex] = temp;
}
}
}
6. Sortierung zusammenführen
Merge Sort ist ein effektiver Sortieralgorithmus, der auf Merge-Operationen basiert. Dieser Algorithmus ist eine sehr typische Anwendung der Divide-and-Conquer-Methode (Divide and Conquer).
Der Vorgang des Zusammenführungsvorgangs ist wie folgt:
Beantragen Sie Speicherplatz, sodass seine Größe der Summe der beiden sortierten Sequenzen entspricht. Dieser Speicherplatz wird zum Speichern der zusammengeführten Sequenz verwendet.
Legen Sie zwei Zeiger fest. Die Anfangspositionen sind die Startpositionen der beiden sortierten Sequenzen.
Vergleichen Sie die Elemente, auf die die beiden Zeiger zeigen, wählen Sie das relativ kleine Element aus, platzieren Sie es im Zusammenführungsbereich und bewegen Sie den Zeiger an die nächste Position.
Wiederholen Sie Schritt 3, bis ein Zeiger das Ende der Sequenz erreicht.
Kopiert alle verbleibenden Elemente der anderen Sequenz direkt an das Ende der zusammengeführten Sequenz.
Kopieren Sie den Codecode wie folgt:
public static int[] mergeSort(int[] arr) {//Merge sort--recursion
if (arr. Länge == 1) {
Rückkehr arr;
}
int half = arr.length / 2;
int[] arr1 = new int[half];
int[] arr2 = new int[arr.length - half];
System.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr, half, arr2, 0, arr2.length);
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
return mergeSortSub(arr1, arr2);
}
private static int[] mergeSortSub(int[] arr1, int[] arr2) {//Sortierunterroutine zusammenführen
int[] result = new int[arr1.length + arr2.length];
int i = 0;
int j = 0;
int k = 0;
while (wahr) {
if (arr1[i] < arr2[j]) {
result[k] = arr1[i];
if (++i > arr1.length - 1) {
brechen;
}
} anders {
result[k] = arr2[j];
if (++j > arr2.length - 1) {
brechen;
}
}
k++;
}
for (; i < arr1.length; i++) {
result[++k] = arr1[i];
}
for (; j < arr2.length; j++) {
result[++k] = arr2[j];
}
Ergebnis zurückgeben;
}
Vollständiger Code (außer QuickSort)
Kopieren Sie den Codecode wie folgt:
Paket com.clzhang.sample.thinking;
import java.util.*;
/**
* Java-Implementierung mehrerer gängiger Sortieralgorithmen
* @author acer
*
*/
öffentliche Klasse CommonSort {
/**
* Der spezifische Algorithmus der Einfügungssortierung wird wie folgt beschrieben:
* 1. Ab dem ersten Element kann davon ausgegangen werden, dass das Element sortiert wurde
* 2. Nehmen Sie das nächste Element heraus und scannen Sie es in der sortierten Elementreihenfolge von hinten nach vorne
* 3. Wenn das Element (sortiert) größer als das neue Element ist, verschieben Sie das Element an die nächste Position
* 4. Wiederholen Sie Schritt 3, bis Sie die Position gefunden haben, an der das sortierte Element kleiner oder gleich dem neuen Element ist
* 5. Nach dem Einfügen des neuen Elements an dieser Position
* 6. Wiederholen Sie die Schritte 2 bis 5
*/
public static void insertSort(int[] data) {
for (int index = 1; index < data.length; index++) {
int key = data[index];
int Position = Index;
// größere Werte nach rechts verschieben
while (position > 0 && data[position - 1] > key) {
Daten[Position] = Daten[Position - 1];
Position--;
}
data[position] = key;
}
}
/**
* Hügelsortierung, Ideen zur Algorithmusimplementierung finden Sie in Wikipedia; geeignet für eine große Anzahl von Sortiervorgängen.
*/
static <E erweitert Comparable<? super E>> void shellSort(List<E> a) {
int h = 1;
while (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) von Knuth,1973>: 1, 4, 13, 40, 121, . ..
für (; h >= 1; h /= 3)
for (int i = h; i < a.size(); i++)
for (int j = i; j >= h && a.get(j).compareTo(a.get(jh)) < 0; j-=h)
Collections.swap(a, j, jh);
}
/**
* Die Funktionsweise des Blasensortierungsalgorithmus ist wie folgt:
* 1. Vergleichen Sie benachbarte Elemente. Wenn das erste größer als das zweite ist, tauschen Sie beide aus.
* 2. Führen Sie die gleiche Arbeit für jedes Paar benachbarter Elemente durch, vom ersten Paar am Anfang bis zum letzten Paar am Ende. Zu diesem Zeitpunkt sollte das letzte Element die größte Zahl sein.
* 3. Wiederholen Sie die obigen Schritte für alle Elemente außer dem letzten.
* 4. Wiederholen Sie die obigen Schritte jedes Mal für immer weniger Elemente, bis keine Zahlenpaare mehr zum Vergleichen vorhanden sind. [1]
*/
public static void bubbleSort(int[] data) {
int temp = 0;
for (int i = data.length - 1; i > 0; --i) {
boolean isSort = false;
for (int j = 0; j < i; ++j) {
if (data[j + 1] < data[j]) {
temp = data[j];
Daten[j] = Daten[j + 1];
data[j + 1] = temp;
isSort = true;
}
}
// Wenn in einer inneren Schleife ein Austausch stattfindet, wird der Vergleich fortgesetzt. Wenn in einer inneren Schleife kein Austausch stattfindet, wird davon ausgegangen, dass er sortiert wurde.
if (!isSort)
brechen;
}
}
/**
* Die Grundidee der Auswahlsortierung ist:
* 1. Wenn i beim Durchlaufen des Arrays die aktuelle Sequenznummer darstellt, die sortiert werden muss, müssen Sie den Mindestwert unter den verbleibenden [i + 1 ... n-1] finden.
* 2. Tauschen Sie dann den gefundenen Minimalwert gegen den Wert aus, auf den i zeigt.
* Da jeder Prozess zum Bestimmen von Elementen einen Unterprozess zum Auswählen des Mindestwerts hat, wird dies allgemein als Auswahlsortierung bezeichnet.
* @param-Daten
*/
public static void selectSort(int[] data) {
int minIndex = 0;
int temp = 0;
for (int i = 0; i < data.length; i++) {
minIndex = i; //Der minimale Datenarray-Index des ungeordneten Bereichs
for (int j = i + 1; j < data.length; j++) { // Finden Sie die kleinsten Daten im ungeordneten Bereich und speichern Sie ihren Array-Index
if (data[j] < data[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) { // Wenn die minimale Position des ungeordneten Bereichs nicht die standardmäßigen ersten Daten sind, tauschen Sie sie aus.
temp = data[i];
data[i] = data[minIndex];
data[minIndex] = temp;
}
}
}
/**
* Der Vorgang des Zusammenführungsvorgangs ist wie folgt:
* 1. Beantragen Sie Speicherplatz, sodass seine Größe der Summe der beiden sortierten Sequenzen entspricht. Dieser Speicherplatz wird zum Speichern der zusammengeführten Sequenz verwendet.
* 2. Setzen Sie zwei Zeiger. Die Anfangspositionen sind die Anfangspositionen der beiden sortierten Sequenzen.
* 3. Vergleichen Sie die Elemente, auf die die beiden Zeiger zeigen, wählen Sie das relativ kleine Element aus, legen Sie es in den Zusammenführungsbereich und bewegen Sie den Zeiger an die nächste Position
* 4. Wiederholen Sie Schritt 3, bis ein Zeiger das Ende der Sequenz erreicht
* 5. Kopieren Sie alle verbleibenden Elemente der anderen Sequenz direkt an das Ende der zusammengeführten Sequenz
*/
public static int[] mergeSort(int[] arr) {//Merge sort--recursion
if (arr. Länge == 1) {
Rückkehr arr;
}
int half = arr.length / 2;
int[] arr1 = new int[half];
int[] arr2 = new int[arr.length - half];
System.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr, half, arr2, 0, arr2.length);
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
return mergeSortSub(arr1, arr2);
}
private static int[] mergeSortSub(int[] arr1, int[] arr2) {//Sortierunterroutine zusammenführen
int[] result = new int[arr1.length + arr2.length];
int i = 0;
int j = 0;
int k = 0;
while (wahr) {
if (arr1[i] < arr2[j]) {
result[k] = arr1[i];
if (++i > arr1.length - 1) {
brechen;
}
} anders {
result[k] = arr2[j];
if (++j > arr2.length - 1) {
brechen;
}
}
k++;
}
for (; i < arr1.length; i++) {
result[++k] = arr1[i];
}
for (; j < arr2.length; j++) {
result[++k] = arr2[j];
}
Ergebnis zurückgeben;
}
private static void printArray(int[] c) {
for (int i = 0; i < c.length; i++)
System.out.print(c[i] + ",");
System.out.println();
}
public static void main(String []args){
int[] data = {10,4,9,23,1,45,27,5,2};
System.out.println("bubbleSort...");
int[] a = data.clone();
printArray(a);
bubbleSort(a);
printArray(a);
System.out.println("selectSort...");
int[] b = data.clone();
printArray(b);
selectSort(b);
printArray(b);
System.out.println("insertionSort...");
int[] c = data.clone();
printArray(c);
insertSort(c);
printArray(c);
System.out.println("shellSort...");
List<Integer> list = new ArrayList<Integer>();
for(int i=0;i<data.length;i++)
list.add(data[i]);
System.out.println(list);
shellSort(list);
System.out.println(list);
System.out.println("mergeSort...");
int[] d = data.clone();
printArray(d);
printArray(mergeSort(d));
}
}