Partage de technologie

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

Préface : Cet article fournit des réponses détaillées à certains doutes concernant l'apprentissage précoce de l'algorithme de tri rapide et fournit une version optimisée de l'algorithme de tri rapide de base.

1. Parlons encore du tri rapide

Le cœur de l’algorithme de tri rapide est分治思想La stratégie diviser pour mieux régner est divisée en trois étapes :

1. Décomposition : décomposer le problème d'origine en plusieurs sous-problèmes similaires et plus petits
2. Solution : si le sous-problème est petit, résolvez-le directement, sinon résolvez le sous-problème de manière récursive ;
3. Fusionner : La solution du problème initial équivaut à la fusion des solutions de plusieurs sous-problèmes.

Appliqué à l'algorithme de tri rapide :

1. Décomposition : l'algorithme de tri rapide souhaite trier l'ensemble du tableau, mais l'échelle est grande, il doit donc trouver un moyen de réduire l'échelle. Sa stratégie de solution consiste à « sélectionner un élément de référence et à diviser le tableau en ; deux parties, avec des éléments à gauche qui sont plus petits que l'élément de référence, tous les éléments à droite sont supérieurs aux éléments de référence. " En répétant le processus ci-dessus, vous pouvez terminer le tri de l'ensemble du tableau. Après avoir terminé cette opération sur l'ensemble du tableau, effectuez le processus ci-dessus respectivement sur les intervalles gauche et droit.
2. Triez rapidement les deux sous-tableaux de manière récursive jusqu'à ce que la longueur de chaque sous-tableau soit 0 ou 1, moment auquel les tableaux sont triés.
3. Étant donné que les sous-tableaux ont été triés séparément lors de la récursion, aucune étape de fusion supplémentaire n'est requise.

2. Implémentation du code et explication détaillée

Le code clé pour le tri rapide est如何根据基准元素划分数组区间(parttion), il existe de nombreuses méthodes de décomposition, une seule méthode est proposée ici.挖坑法
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

---

Réponses détaillées :
1.Pourquoistart>=endEst-ce la condition finale de la récursion ?

Décomposez continuellement le sous-problème. La taille finale du sous-problème est de 1, c'est-à-dire qu'il n'y a qu'un seul élément. Il n'est pas nécessaire de continuer la décomposition pour le moment. Les pointeurs de début et de fin pointent vers l'élément en même temps. temps.

2. Pourquoi la droite devrait-elle passer en premier plutôt que la gauche ?

Cela dépend de qui commence基准元素的位置,Dans le code ci-dessus, l'élément de base (clé) est l'élément le plus à gauche s'il est déplacé en premier.left, la gauche rencontre d'abord un élément plus grand que l'élément de base, puis exécutearr[right] = arr[left], parce que je n'ai pas sauvegardéarr[right], cet élément sera perdu
Si vous allez d'abord à droite, la droite rencontre d'abord un élément plus petit que l'élément de base, puis exécutearr[left]=arr[right], parce que la gauche n'a pas bougé à ce moment, c'est toujours le pivot, mais le pivot a été sauvegardé par nos soins à l'aide de la clé.

3.Pourquoi arr[right]>=key ?>N'est-ce pas possible ?

Supérieur ou égal à est principalement destiné au traitement重复元素问题
Par exemple, il existe un tableau[6,6,6,6,6]Si c'est >, le pointeur droit ne bougera pas, et le pointeur gauche ne bougera pas non plus, et il sera coincé dans une boucle infinie.

4. Pourquoi est-ce appelé méthode de creusement de fosses ?

Lorsque le pointeur r rencontre le premierarr[r] = arr[l], à ce moment, la position l est vide, formant un creux.

---

3. Optimisation du tri rapide

Il existe deux directions principales d'optimisation :

1. Il peut être prouvé que la sélection du pivot de la valeur de référence est que lorsque la valeur de référence est sélectionnée au hasard, la complexité temporelle des approches de tri rapideO(N*logN), c'est-à-dire la meilleure complexité temporelle
2. Traitement des éléments répétés : s'il y a un grand nombre d'éléments répétés dans l'intervalle, la version ci-dessus de l'algorithme de tri rapide répétera les mêmes éléments plusieurs fois afin de réduire les opérations redondantes, utilisez ;数组分三块Dans le même temps, si vous rencontrez des cas de tests particuliers (tableau séquentiel ou tableau inversé), la complexité temporelle se dégradera àO(N^2)

Tout d'abord, sur la base d'une question (trier par couleur) comprendre ce que c'est数组分三块
analyser

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

• Avisl,r的起始位置, le premier élément et le dernier élément appartiennent à未处理状态, donc `l, r ne peut pas pointer vers ces deux éléments et doit être en dehors de l'intervalle
• Le soi-disant tableau est divisé en trois parties, ce qui signifie utiliser三个指针去分别维护四个区间, l'un des intervalles est未处理区间, à mesure que le pointeur cur continue de se déplacer, tous les intervalles sont traités et finalement il n'y a que trois intervalles.

Appliquez les idées ci-dessus à快速排序的parttion中, le résultat final est divisé en trois intervalles

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. Sélectionnez au hasard la valeur de base
Sélectionnez au hasard la valeur de base en utilisant des nombres aléatoires

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

1
2
3

Code amélioré complet :

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

• Efficacité considérablement améliorée

4. Algorithme de sélection rapide

L'algorithme de sélection rapide est基于快速排序优化版本Une complexité temporelle deO(N)L'algorithme de sélection, le scénario d'utilisation est第K大/前K大des problèmes de choix comme

01.Le Kème plus grand élément du tableau
Lien : https://leetcode.cn/problems/kth-largest-element-in-an-array/
analyser

• La solution par force brute consiste à l'utiliser directementsortTrier puis revenir au Kième plus grand
• complexité temporelle :O(N*logN)
• Complexité spatiale :O(logN)Appels de pile générés par récursion

Ensuite, un algorithme de sélection rapide est utilisé pour implémenterO(N)La complexité temporelle de
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

• L'idée de l'algorithme de sélection rapide est très similaire à celle du tri rapide. La différence est que l'algorithme de sélection rapide ne récure qu'une partie de l'intervalle de chaque résultat de partition, au lieu de récurer l'intégralité de l'intervalle comme le tri rapide, donc le la complexité temporelle de l'algorithme de sélection rapide est réduite.O(N)