Quick Sort (QuickSort) – Java-Implementierung

Hintergrund

Quick Sort ist eine Sortiermethode, die in den 1960er Jahren vom Amerikaner Tony Hall vorgeschlagen wurde. Dieses Sortierverfahren war schon damals ein sehr schnelles Sortierverfahren. Daher wird es in Bezug auf die Benennung als „Schnellsortierung“ bezeichnet. Dieser Algorithmus ist einer der sieben wichtigsten Algorithmen des 20. Jahrhunderts. Die durchschnittliche Zeitkomplexität beträgt Ο(nlogn), und im Fall von O(nlogn) ist die tatsächliche Operationsgeschwindigkeit schneller als bei anderen Sortiermethoden mit derselben Zeitkomplexität .

Studenten, die sich für Tony Hall und den Hintergrund des Schnellsortierens interessieren, können diese Einführung lesen: http://www.nowamagic.net/librarys/veda/detail/2391

Sortieridee

Die Idee der schnellen Sortierung ist schwer vorstellbar, aber sehr leicht zu verstehen

Seine Idee ist diese:

1 Wählen Sie zuerst die Warteschlange aus, a Ein bestimmtes Element ist der Basiswert (normalerweise wird das Kopfelement oder das Schwanzelement ausgewählt).

2. Vergleichen Sie den Basiswert mit allen Elementen der Reihe nach. Die Elemente werden entsprechend den Vergleichsergebnissen in zwei Warteschlangen A und B aufgeteilt. Eines, bei dem alle Elemente größer als der Basiswert sind, und eines, bei dem alle Elemente kleiner als der Basiswert sind.

3. Verwenden Sie A als neue Warteschlange, wählen Sie die Basis erneut aus und teilen Sie sie dann in zwei kleinere Warteschlangen auf.

4 Teilen Sie auf diese Weise weiterhin jede kleine Warteschlange in unendlich auf zwei Warteschlangen.

5. Bis eine Warteschlange in Teile aufgeteilt wurde, die nicht entpackt werden können (d. h. ein Element)

6 Weil die Reihenfolge zwischen den Warteschlangen festgelegt ist. Kombinieren Sie diese Warteschlangen auf einmal, und die Gesamtsortierung ist abgeschlossen.

(Anti-Diebstahl-Verbindung: Dieser Artikel wurde zuerst von http://www.cnblogs.com/jilodream/ veröffentlicht)

Beachten Sie, dass es hier zwei Kernschritte gibt, nämlich

1, wählen Sie das Wertelement aus, teilen Sie die gesamte Warteschlange in zwei Unterwarteschlangen

2. Verwenden Sie dann die Unterwarteschlange als neue Warteschlange mit einer Gesamtgröße, die kleiner als die aktuelle ist, wieder. und Berechnungen durchführen, bis die Berechnung abgeschlossen ist. Bisher ist es sehr einfach.

Diese beiden Kernschritte schaffen die inhärenten Vorteile der schnellen Sortierung:

1. Durch den Vergleich der Größe der in Unterwarteschlangen unterteilten Elemente wird im zukünftigen Vergleichsprozess der Vergleichsbereich dieses Elements immer ermittelt Bleiben Sie in dieser Unterwarteschlange und führen Sie keine unnötigen Vergleiche mehr durch. Dadurch können frühe Vergleiche noch einen starken Einfluss auf spätere Vergleiche haben. Ähnlich wie bei der Blasensortierungsmethode haben viele Vergleiche im frühen Stadium nur sehr geringe Auswirkungen auf das spätere Stadium. Dies ist dem kmp-Algorithmus sehr ähnlich. Der frühe Vergleich sollte versuchen, den größtmöglichen Nutzen zu erzielen.

2. Teilen Sie die ursprüngliche Waagenwarteschlange in mehrere kleine Unterwarteschlangen auf (Anti-Diebstahl-Verbindung: Dieser Artikel wurde zuerst von http://www.cnblogs.com/jilodream veröffentlicht /) Das gelöste Problem ist das gleiche wie bei der ursprünglichen Warteschlange, der Maßstab ist jedoch kleiner. Eine solche ständige Spaltung führt zu einer Teile-und-Herrsche-Mentalität. Diese Idee stimmt auch mit dem Rucksackalgorithmus überein.

Für Schüler, die Schwierigkeiten haben, Text zu verstehen, können Sie sich dieses klassische dynamische Bild im Internet ansehen, das sehr anschaulich ist:

Das Folgende ist in Java-Code implementiert

import java.util.Arrays;

public class QuickSort
{
    public static void main(String args[])
    {
        QuickSort quicksort = new QuickSort();
        int[] arrays = new int[]
        { 1, 12, 2, 13, 3, 14, 4, 15, 5, 16, 17, 17, 177, 18, 8, 8, 19 };
        quicksort.quickSort(arrays);
        System.out.println(Arrays.toString(arrays));
    }
    
    private void quickSort(int[] arrays)
    {
        subQuickSort(arrays, 0, arrays.length - 1);
    }
    
    private void subQuickSort(int[] arrays, int start, int end)
    {
        if (start >= end)
        {
            return;
        }
        int middleIndex = subQuickSortCore(arrays, start, end);
        subQuickSort(arrays, start, middleIndex - 1);
        subQuickSort(arrays, middleIndex + 1, end);
    }
    
    private int subQuickSortCore(int[] arrays, int start, int end)
    {
        int middleValue = arrays[start];
        while (start < end)
        {
            while (arrays[end] >= middleValue && start < end)
            {
                end--;
            }
            arrays[start] = arrays[end];
            while (arrays[start] <= middleValue && start < end)
            {
                start++;
            }
            arrays[end] = arrays[start];
        }
        arrays[start] = middleValue;
        return start;
    }
}