Compartilhamento de tecnologia

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

Prefácio: Este artigo fornece respostas detalhadas a algumas dúvidas sobre o aprendizado inicial do algoritmo de classificação rápida e fornece uma versão otimizada do algoritmo básico de classificação rápida.

1. Vamos falar novamente sobre classificação rápida

O núcleo do algoritmo de classificação rápida é分治思想A estratégia de dividir para conquistar é dividida nas três etapas a seguir:

1. Decomposição: decompor o problema original em vários subproblemas menores e semelhantes
2. Solução: Se o subproblema for pequeno, resolva-o diretamente, caso contrário, resolva o subproblema recursivamente;
3. Mesclar: A solução do problema original é igual à fusão das soluções de vários subproblemas.

Aplicado ao algoritmo de classificação rápida:

1. Decomposição: O que o algoritmo de classificação rápida deseja alcançar é classificar todo o array, mas a escala é grande, então ele precisa encontrar uma maneira de reduzir a escala. Sua estratégia de solução é "selecionar um elemento de referência e dividir o array em; duas partes, com elementos à esquerda menores que o elemento de referência, todos os elementos à direita são maiores que os elementos de referência." Repetindo o processo acima, você pode concluir a classificação de todo o array. Depois de concluir esta operação uma vez para toda a matriz, execute o processo acima para os intervalos esquerdo e direito, respectivamente.
2. Classifique rapidamente as duas submatrizes recursivamente até que o comprimento de cada submatriz seja 0 ou 1, ponto em que as matrizes são classificadas.
3. Como as submatrizes foram classificadas separadamente durante a recursão, nenhuma etapa adicional de fusão é necessária.

2. Implementação do código e explicação detalhada

O código-chave para classificação rápida é如何根据基准元素划分数组区间(parttion), existem muitos métodos de decomposição, apenas um método é fornecido aqui.挖坑法
Código:

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

---

Respostas detalhadas:
1. Por questart>=endÉ a condição final da recursão?

Decomponha continuamente o subproblema. O tamanho final do subproblema é 1, ou seja, há apenas um elemento. Não há necessidade de continuar a decomposição neste momento. tempo.

2. Por que a direita deveria ir primeiro em vez da esquerda?

Depende de quem vai primeiro基准元素的位置,No código acima, o elemento base (chave) é o elemento mais à esquerda se for movido primeiro.left, left primeiro encontra um elemento maior que o elemento base e depois executaarr[right] = arr[left],por não salvararr[right], este elemento será perdido
Se você for para a direita primeiro, a direita primeiro encontrará um elemento menor que o elemento base e depois executaráarr[left]=arr[right], porque a esquerda não se moveu neste momento, ainda é o pivô, mas o pivô foi salvo por nós usando a tecla.

3.Por que arr[right]>=key?>Não é possível?

Maior ou igual a é principalmente para processamento重复元素问题
Por exemplo, existe uma matriz[6,6,6,6,6]Se for >, o ponteiro direito não se moverá e o ponteiro esquerdo também não se moverá e ficará preso em um loop infinito.

4. Por que isso é chamado de escavação?

Quando o ponteiro r encontra o primeiroarr[r] = arr[l], neste momento, a posição l fica em branco, formando um buraco.

---

3. Otimização de classificação rápida

Existem duas direções principais de otimização:

1. Pode-se provar que a seleção do pivô do valor de referência é que, quando o valor de referência é selecionado aleatoriamente, a complexidade de tempo da classificação rápida se aproximaO(N*logN), ou seja, a melhor complexidade de tempo
2. Processamento de elementos repetidos: Se houver um grande número de elementos repetidos dentro do intervalo, a versão acima do algoritmo de classificação rápida repetirá os mesmos elementos várias vezes para reduzir operações redundantes;数组分三块Ao mesmo tempo, se você encontrar casos de teste especiais (matriz sequencial ou matriz reversa), a complexidade do tempo será reduzida paraO(N^2)

Primeiro, com base em uma pergunta (classificar por cor) entender o que é数组分三块
analisar

Código:

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

• Perceberl,r的起始位置, o primeiro elemento e o último elemento pertencem a未处理状态, então `l, r não pode apontar para esses dois elementos e deve estar fora do intervalo
• O chamado array é dividido em três partes, o que significa usar三个指针去分别维护四个区间, um dos intervalos é未处理区间, à medida que o ponteiro cur continua a se mover, todos os intervalos são processados ​​e, finalmente, existem apenas três intervalos.

Aplique as idéias acima para快速排序的parttion中, o resultado final é dividido em três intervalos

Código:

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. Selecione aleatoriamente o valor base
Selecione aleatoriamente o valor base usando números aleatórios

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

1
2
3

Código melhorado 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

• Eficiência melhorou significativamente

4. Algoritmo de seleção rápida

O algoritmo de seleção rápida é基于快速排序优化版本Uma complexidade de tempo deO(N)O algoritmo de seleção, o cenário de uso é第K大/前K大questões de escolha como

01.O K-ésimo maior elemento da matriz
Link: https://leetcode.cn/problems/kth-largest-element-in-an-array/
analisar

• A solução de força bruta é usá-la diretamentesortClassifique e retorne ao K-ésimo maior
• complexidade de tempo:O(N*logN)
• Complexidade do espaço:O(logN)Chamadas de pilha geradas por recursão

A seguir, um algoritmo de seleção rápida é usado para implementarO(N)A complexidade do tempo
Código:

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

• A ideia do algoritmo de seleção rápida é muito semelhante à da classificação rápida. A diferença é que o algoritmo de seleção rápida recorre apenas a uma parte do intervalo de cada resultado da partição, em vez de recorrer ao intervalo inteiro como a classificação rápida. a complexidade de tempo do algoritmo de seleção rápida é reduzida.O(N)