Was ist die Idee, einen Schnellsortierungsalgorithmus in Java zu implementieren?

1. Was ist der Schnellsortierungsalgorithmus

Tatsächlich ist die Schnellsortierung eine Verbesserung gegenüber der Blasensortierung.

2. Die Idee des Schnellsortierungsalgorithmus

Teilen Sie die zu sortierenden Daten durch eine Sortierung in zwei unabhängige Teile auf, und alle Daten in einem Teil sind höher als alle Die Daten im anderen Teil sollten klein sein. Anschließend können die beiden Teile der Daten mit dieser Methode schnell sortiert werden, sodass die gesamten Daten zu einer geordneten Sequenz werden.

(Empfohlenes Video-Tutorial: Java-Video-Tutorial )

3. Implementierungsideen

(1) Nehmen Sie das erste Schlüsselwort K 1 als Kontrollwörter , teilen Sie [K 1 ,K 2 ,…,K n ] in zwei Unterbereiche auf, sodass alle Schlüsselwörter im linken Bereich kleiner oder gleich K 1 sind, alle Schlüsselwörter im rechten Bereich größer oder gleich K sind 1 und schließlich befindet sich das Steuerwort in der Mitte der beiden Teilbereiche. Die Daten im Unterbereich befinden sich noch in einem ungeordneten Zustand. ;

(2) Behandeln Sie den linken Bereich als Ganzes und verwenden Sie die Schritte in (1), um ihn zu verarbeiten, und führen Sie die gleiche Verarbeitung im rechten Bereich durch. (d. h. Rekursion)

(3) Wiederholen Sie die Schritte (1) und (2), bis der linke Bereich verarbeitet ist.

4. Implementierungscode

static void quicksort(int n[], int left, int right) {
        int dp;
        if (left < right) {
            dp = partition(n, left, right);
            quicksort(n, left, dp - 1);
            quicksort(n, dp + 1, right);
        }
    }
 
    static int partition(int n[], int left, int right) {
        int pivot = n[left];
        while (left < right) {
            while (left < right && n[right] >= pivot)
                right--;
            if (left < right)
                n[left++] = n[right];
            while (left < right && n[left] <= pivot)
                left++;
            if (left < right)
                n[right--] = n[left];
        }
        n[left] = pivot;
        return left;
    }

Empfohlenes Tutorial: Java-Eingabeprogramm

Das obige ist der detaillierte Inhalt vonWas ist die Idee, einen Schnellsortierungsalgorithmus in Java zu implementieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!