Condivisione della tecnologia

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

Prefazione: questo articolo fornisce risposte dettagliate ad alcuni dubbi sull'apprendimento precoce dell'algoritmo di ordinamento rapido e fornisce una versione ottimizzata dell'algoritmo di ordinamento rapido di base.

1. Parliamo ancora dell'ordinamento rapido

Il nucleo dell'algoritmo di ordinamento rapido è分治思想La strategia “divide et impera” è suddivisa nei seguenti tre passaggi:

1. Scomposizione: scompone il problema originale in diversi sottoproblemi simili e più piccoli
2. Soluzione: se il sottoproblema è piccolo, risolvilo direttamente, altrimenti risolvilo ricorsivamente
3. Unisci: la soluzione del problema originale equivale alla fusione delle soluzioni di più sottoproblemi.

Applicato all'algoritmo di ordinamento rapido:

1. Decomposizione: ciò che l'algoritmo di ordinamento rapido vuole ottenere è ordinare l'intero array, ma la scala è grande, quindi è necessario trovare un modo per ridurre la scala. La sua strategia di soluzione è "selezionare un elemento di riferimento e dividere l'array in due parti, con elementi a sinistra inferiori all'elemento benchmark, tutti gli elementi a destra sono maggiori degli elementi di riferimento." Ripetendo il processo sopra descritto, è possibile completare l'ordinamento dell'intero array. Dopo aver completato questa operazione una volta per l'intero array, eseguire la procedura sopra descritta rispettivamente per gli intervalli sinistro e destro.
2. Ordina rapidamente i due sottoarray in modo ricorsivo fino a quando la lunghezza di ciascun sottoarray è 0 o 1, a quel punto gli array vengono ordinati.
3. Poiché i sottoarray sono stati ordinati separatamente durante la ricorsione, non è richiesto alcun ulteriore passaggio di fusione.

2. Implementazione del codice e spiegazione dettagliata

Il codice chiave per l'ordinamento rapido è如何根据基准元素划分数组区间(parttion), esistono molti metodi di scomposizione, qui viene fornito solo un metodo.挖坑法
Codice:

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

---

Risposte dettagliate:
1.Perchéstart>=endÈ la condizione finale della ricorsione?

Scomporre continuamente il sottoproblema. La dimensione finale del sottoproblema è 1, ovvero c'è un solo elemento. Non è necessario continuare la scomposizione in questo momento. I puntatori di inizio e fine puntano allo stesso elemento tempo.

2. Perché dovrebbe andare prima la destra invece della sinistra?

Dipende da chi inizia per primo基准元素的位置,Nel codice precedente, l'elemento base (chiave) è l'elemento più a sinistra se viene spostato per primoleft, left incontra prima un elemento più grande dell'elemento base e quindi eseguearr[right] = arr[left],a causa del mancato salvataggioarr[right], questo elemento andrà perso
Se vai prima a destra, destra incontra prima un elemento più piccolo dell'elemento base e poi eseguearr[left]=arr[right], poiché la sinistra non si è mossa in questo momento, è ancora il perno, ma il perno è stato salvato da noi utilizzando la chiave.

3.Perché arr[right]>=key?>Non è possibile?

Maggiore o uguale a serve principalmente per l'elaborazione重复元素问题
Ad esempio, c'è un array[6,6,6,6,6]Se è >, il puntatore destro non si sposterà, e neanche il puntatore sinistro si sposterà, e sarà bloccato in un ciclo infinito.

4. Perché si chiama metodo di scavo?

Quando il puntatore r incontra il primoarr[r] = arr[l], in questo momento, la posizione l è vuota e forma una fossa.

---

3. Ottimizzazione dell'ordinamento rapido

Esistono due direzioni principali di ottimizzazione:

1. È possibile dimostrare che la selezione del perno del valore di riferimento è tale che, quando il valore di riferimento viene selezionato in modo casuale, la complessità temporale dell'ordinamento rapido si avvicinaO(N*logN), cioè la migliore complessità temporale
2. Elaborazione di elementi ripetuti: se è presente un numero elevato di elementi ripetuti nell'intervallo, la versione precedente dell'algoritmo di ordinamento rapido ripeterà gli stessi elementi più volte per ridurre le operazioni ridondanti, utilizzare数组分三块Allo stesso tempo, se si incontrano casi di test speciali (array sequenziale o array inverso), la complessità temporale diminuiràO(N^2)

Innanzitutto, sulla base di una domanda (ordinare per colore) capire di cosa si tratta数组分三块
analizzare

Codice:

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

• Avvisol,r的起始位置, a cui appartengono il primo elemento e l'ultimo elemento未处理状态, quindi `l, r non possono puntare a questi due elementi e devono essere al di fuori dell'intervallo
• Il cosiddetto array è diviso in tre parti, il che significa utilizzare三个指针去分别维护四个区间, uno degli intervalli è未处理区间, man mano che il puntatore continua a spostarsi, tutti gli intervalli vengono elaborati e infine ci sono solo tre intervalli.

Applica le idee di cui sopra a快速排序的parttion中, il risultato finale è diviso in tre intervalli

Codice:

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. Selezionare casualmente il valore base
Seleziona casualmente il valore base utilizzando numeri casuali

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

1
2
3

Codice migliorato completo:

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

• L'efficienza è notevolmente migliorata

4. Algoritmo di selezione rapida

L'algoritmo di selezione rapida è基于快速排序优化版本Una complessità temporale diO(N)L'algoritmo di selezione, lo scenario di utilizzo è第K大/前K大questioni di scelta come

01.Il K-esimo elemento più grande dell'array
Collegamento: https://leetcode.cn/problems/kth-largest-element-in-an-array/
analizzare

• La soluzione della forza bruta è usarla direttamentesortOrdina e poi torna al K-esimo più grande
• complessità temporale:O(N*logN)
• Complessità spaziale:O(logN)Chiamate stack generate dalla ricorsione

Successivamente, viene utilizzato un algoritmo di selezione rapida per l'implementazioneO(N)La complessità temporale di
Codice:

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'idea dell'algoritmo di selezione rapida è molto simile a quella dell'ordinamento rapido. La differenza è che l'algoritmo di selezione rapida ricorre solo su una parte dell'intervallo di ciascun risultato della partizione, invece di ripetere l'intero intervallo come l'ordinamento rapido. la complessità temporale dell'algoritmo di selezione rapida è ridottaO(N)