Technologieaustausch

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Vorwort: Dieser Artikel gibt detaillierte Antworten auf einige Zweifel am frühen Lernen des Schnellsortierungsalgorithmus und stellt eine optimierte Version des grundlegenden Schnellsortierungsalgorithmus bereit.

1. Lassen Sie uns noch einmal über die schnelle Sortierung sprechen

Der Kern des Schnellsortierungsalgorithmus ist分治思想Die Divide-and-Conquer-Strategie gliedert sich in die folgenden drei Schritte:

1. Zerlegung: Zerlegen Sie das ursprüngliche Problem in mehrere ähnliche, kleinere Teilprobleme
2. Lösung: Wenn das Teilproblem klein ist, lösen Sie es direkt; andernfalls lösen Sie das Teilproblem rekursiv
3. Zusammenführen: Die Lösung des ursprünglichen Problems entspricht der Zusammenführung der Lösungen mehrerer Teilprobleme.

Auf den Schnellsortierungsalgorithmus angewendet:

1. Zerlegung: Der Schnellsortierungsalgorithmus möchte das gesamte Array sortieren, aber der Maßstab ist groß, daher muss er einen Weg finden, den Maßstab zu reduzieren. Seine Lösungsstrategie besteht darin, „ein Benchmark-Element auszuwählen und das Array aufzuteilen“. zwei Teile, mit Elementen auf der linken Seite, die kleiner als das Benchmark-Element sind, alle Elemente auf der rechten Seite sind größer als die Referenzelemente.“ Durch Wiederholen des obigen Vorgangs können Sie die Sortierung des gesamten Arrays abschließen. Nach Abschluss dieses Vorgangs am Führen Sie für das gesamte Array den obigen Vorgang jeweils für das linke und das rechte Intervall aus.
2. Sortieren Sie die beiden Subarrays schnell und rekursiv, bis die Länge jedes Subarrays 0 oder 1 beträgt. An diesem Punkt werden die Arrays sortiert.
3. Da die Subarrays während der Rekursion separat sortiert wurden, ist kein zusätzlicher Zusammenführungsschritt erforderlich.

2. Code-Implementierung und detaillierte Erläuterung

Der Schlüsselcode für die schnelle Sortierung lautet如何根据基准元素划分数组区间(parttion)Es gibt viele Zerlegungsmethoden, hier wird nur eine Methode bereitgestellt.挖坑法
Code:

class Solution {
    public int[] sortArray(int[] nums) {
        quick(nums, 0, nums.length - 1);
        return nums;
    }

    private void quick(int[] arr, int start, int end) {
        if(start >= end) return;// 递归结束条件
        int pivot = parttion(arr, start, end);
		
		// 递归解决子问题
        quick(arr, start, pivot - 1);
        quick(arr, pivot + 1, end);
    }

	
	// 挖坑法进行分解
    private int parttion(int[] arr, int left, int right) {
        int key = arr[left];
        while(left < right) {
            while(left < right && arr[right] >= key) right--;
            arr[left] = arr[right];
            while(left < right && arr[left] <= key) ++left;
            arr[right] = arr[left];
        }
        arr[left] = key;
        return left;
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---

Ausführliche Antworten:
1.Warumstart>=endIst es die Endbedingung der Rekursion?

Zerlegen Sie das Unterproblem kontinuierlich. Die endgültige Größe des Unterproblems beträgt 1, das heißt, es gibt zu diesem Zeitpunkt keine Notwendigkeit, die Zerlegung fortzusetzen Zeit.

2. Warum sollte die Rechte zuerst gehen und nicht die Linke?

Es kommt darauf an, wer zuerst geht基准元素的位置,Im obigen Code ist das Basiselement (Schlüssel) das Element ganz links, wenn es zuerst verschoben wirdleft, stößt zuerst auf ein Element, das größer als das Basiselement ist, und führt es dann ausarr[right] = arr[left],weil nicht gespeichert wurdearr[right], geht dieses Element verloren
Wenn Sie zuerst nach rechts gehen, trifft rechts zuerst auf ein Element, das kleiner als das Basiselement ist, und führt es dann ausarr[left]=arr[right]Da sich die linke Seite zu diesem Zeitpunkt nicht bewegt hat, ist sie immer noch der Drehpunkt, aber der Drehpunkt wurde von uns mit dem Schlüssel gespeichert.

3.Warum ist arr[right]>=key?>Ist das nicht möglich?

Größer oder gleich dient hauptsächlich der Verarbeitung重复元素问题
Es gibt zum Beispiel ein Array[6,6,6,6,6]Wenn es > ist, bewegt sich der rechte Zeiger nicht und auch der linke Zeiger bewegt sich nicht und bleibt in einer Endlosschleife hängen.

4. Warum heißt es Grubengrabungsmethode?

Wenn der R-Zeiger auf den ersten trifftarr[r] = arr[l]Zu diesem Zeitpunkt ist die l-Position leer und bildet eine Grube.

---

3. Optimierung der Schnellsortierung

Es gibt zwei Hauptoptimierungsrichtungen:

1. Es kann bewiesen werden, dass die Auswahl des Benchmark-Wert-Pivots so ist, dass sich die zeitliche Komplexität der schnellen Sortierung nähert, wenn der Benchmark-Wert zufällig ausgewählt wirdO(N*logN), also die beste Zeitkomplexität
2. Verarbeitung wiederholter Elemente: Wenn innerhalb des Intervalls eine große Anzahl wiederholter Elemente vorhanden ist, wird die obige Version des Schnellsortierungsalgorithmus dieselben Elemente mehrmals wiederholen, um redundante Vorgänge zu reduzieren数组分三块Wenn Sie gleichzeitig auf spezielle Testfälle (sequentielles Array oder umgekehrtes Array) stoßen, verringert sich die Zeitkomplexität aufO(N^2)

Zunächst basierend auf einer Frage (nach Farbe sortieren) verstehen, was ist数组分三块
analysieren

Code:

class Solution {
    public void sortColors(int[] nums) {
        // 分治 --
        // 1.定义三指针
        int i = 0;// 遍历整个数组
        int l = -1, r = nums.length;

        while(i < r) {
            if(nums[i] == 0) swap(nums,++l,i++);
            else if(nums[i] == 1) i++;
            else swap(nums,--r,i);
        }
        return;
    }

    private void swap(int[] nums,int x,int y) {
        int tmp = nums[x]; nums[x] = nums[y]; nums[y] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• Beachtenl,r的起始位置, das erste Element und das letzte Element gehören dazu未处理状态, also kann `l, r nicht auf diese beiden Elemente zeigen und muss außerhalb des Intervalls liegen
• Das sogenannte Array ist in drei Teile unterteilt, was bedeutet, dass es verwendet wird三个指针去分别维护四个区间, eines der Intervalle ist未处理区间Während sich der Cur-Zeiger weiter bewegt, werden alle Intervalle verarbeitet, und schließlich sind nur noch drei Intervalle vorhanden.

Wenden Sie die oben genannten Ideen an快速排序的parttion中, das Endergebnis wird in drei Intervalle unterteilt

Code:

class Solution {
    // 快速排序优化版
    // 分解--解决--合并
    public int[] sortArray(int[] nums) {
        qsort(nums, 0, nums.length - 1);
        return nums;
    }

    private void qsort(int[] nums, int start, int end) {
        if(start >= end) return;// 递归结束条件
        // 分解
        int pivot = nums[start];
        int l = start - 1, r = end + 1, i = start;
        while(i < r) {
            int cur = nums[i];
            if(cur < pivot) swap(nums, ++l, i++);
            else if(cur == pivot) ++i;
            else swap(nums, --r, i);
        }

        // [start, l]  [l+1, r-1]  [r, end]
        // 递归解决
        qsort(nums, start, l);
        qsort(nums, r, end);
    }

    private void swap(int[] nums,int i, int j) {
        int tmp = nums[i];  nums[i] = nums[j]; nums[j] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

2. Wählen Sie den Basiswert zufällig aus
Wählen Sie den Basiswert zufällig mithilfe von Zufallszahlen aus

        int pivot = nums[start + new Random().nextInt(end - start + 1)];
        //               起始位置      随机产生的偏移量

1
2
3

Komplett verbesserter Code:

class Solution {
    // 快速排序优化版
    // 分解--解决--合并
    public int[] sortArray(int[] nums) {
        qsort(nums, 0, nums.length - 1);
        return nums;
    }

    private void qsort(int[] nums, int start, int end) {
        if(start >= end) return;// 递归结束条件
        // 分解
        int pivot = nums[start + new Random().nextInt(end - start + 1)];
        int l = start - 1, r = end + 1, i = start;
        while(i < r) {
            int cur = nums[i];
            if(cur < pivot) swap(nums, ++l, i++);
            else if(cur == pivot) ++i;
            else swap(nums, --r, i);
        }

        // [start, l]  [l+1, r-1]  [r, end]
        // 递归解决
        qsort(nums, start, l);
        qsort(nums, r, end);
    }

    private void swap(int[] nums,int i, int j) {
        int tmp = nums[i]; 
        nums[i] = nums[j]; 
        nums[j] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

• Effizienz deutlich verbessert

4. Schnellauswahlalgorithmus

Der Schnellauswahlalgorithmus ist基于快速排序优化版本Eine zeitliche Komplexität vonO(N)Der Auswahlalgorithmus ist das Nutzungsszenario第K大/前K大Auswahlfragen wie

01. Das K-te größte Element im Array
Link: https://leetcode.cn/problems/kth-largest-element-in-an-array/
analysieren

• Die Brute-Force-Lösung besteht darin, es direkt zu verwendensortSortieren Sie und kehren Sie dann zum K-ten Größten zurück
• Zeitkomplexität:O(N*logN)
• Raumkomplexität:O(logN)Durch Rekursion generierte Stapelaufrufe

Als nächstes wird zur Implementierung ein Schnellauswahlalgorithmus verwendetO(N)Die zeitliche Komplexität von
Code:

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return qsort(nums, 0, nums.length - 1, k);
    }

    private int qsort(int[] nums, int start, int end, int k) {
        if(start >= end) return nums[start];
        int pivot = nums[start + new Random().nextInt(end - start + 1)];
		
		// 数组分三块  <pivot  ==pivot  >pivot
        int l = start - 1, r = end + 1, i = start;
        while(i < r) {
            if(nums[i] < pivot) swap(nums, ++l, i++);
            else if(nums[i] == pivot) ++i;
            else swap(nums, --r, i);
        }

        // [start, l]  [l+1, r - 1]  [r, end]
        int c = end - r + 1, b = r - 1 - (l + 1) + 1, a = l - start + 1;
        // 分情况讨论  进行选择
        if(c >= k) return qsort(nums, r, end, k);
        else if(b + c >= k) return pivot;
        else return qsort(nums, start, l, k - b - c);// 找较小区间的第(k-b-c)大
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

• Die Idee des Schnellauswahlalgorithmus ist der der Schnellsortierung sehr ähnlich. Der Unterschied besteht darin, dass der Schnellauswahlalgorithmus nur einen Teil des Intervalls jedes Partitionsergebnisses rekursiert, anstatt wie bei der Schnellsortierung das gesamte Intervall Die Zeitkomplexität des Schnellauswahlalgorithmus wird reduziertO(N)