Serie de algoritmos: clasificación divide y vencerás|Rediscusión sobre la clasificación rápida|Optimización de la clasificación rápida|Algoritmo de selección rápida

2024-07-12

Prefacio: este artículo proporciona respuestas detalladas a algunas dudas sobre el aprendizaje temprano del algoritmo de clasificación rápida y proporciona una versión optimizada del algoritmo de clasificación rápida básica.

1. Hablemos nuevamente de clasificación rápida

El núcleo del algoritmo de clasificación rápida es分治思想La estrategia divide y vencerás se divide en los siguientes tres pasos:

Descomposición: descomponer el problema original en varios subproblemas similares y más pequeños.
Solución: si el subproblema es pequeño, resuélvalo directamente; de lo contrario, resuelva el subproblema de forma recursiva;
Fusionar: La solución del problema original es igual a la fusión de las soluciones de varios subproblemas.

Aplicado al algoritmo de clasificación rápida:

Descomposición: lo que el algoritmo de clasificación rápida quiere lograr es ordenar toda la matriz, pero la escala es grande, por lo que necesita encontrar una manera de reducir la escala. Su estrategia de solución es "seleccionar un elemento de referencia y dividir la matriz en; dos partes, con elementos a la izquierda que son más pequeños que el elemento de referencia, todos los elementos a la derecha son mayores que los elementos de referencia". Al repetir el proceso anterior, puede completar la clasificación de toda la matriz. Después de completar esta operación en toda la matriz, realice el proceso anterior en los intervalos izquierdo y derecho respectivamente.
Ordene rápidamente los dos subarreglos de forma recursiva hasta que la longitud de cada subarreglo sea 0 o 1, momento en el cual se ordenan los arreglos.
Dado que los subarreglos se ordenaron por separado durante la recursividad, no se requiere ningún paso de fusión adicional.

2. Implementación del código y explicación detallada.

El código clave para la clasificación rápida es如何根据基准元素划分数组区间(parttion)Hay muchos métodos de descomposición, aquí solo se proporciona uno.挖坑法
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

Respuestas detalladas:
1.Por quéstart>=end¿Es la condición final de la recursividad?

Descomponer continuamente el subproblema. El tamaño final del subproblema es 1, es decir, solo hay un elemento. No es necesario continuar descomponiendo en este momento. Los punteros de inicio y fin apuntan al elemento al mismo tiempo. tiempo.

2. ¿Por qué debería ir primero la derecha y no la izquierda?

Depende de quien vaya primero基准元素的位置En el código anterior, el elemento base (clave) es el elemento más a la izquierda si se mueve primero.left, la izquierda primero encuentra un elemento más grande que el elemento base y luego ejecutaarr[right] = arr[left],por no guardararr[right], este elemento se perderá
Si va primero a la derecha, la derecha primero encontrará un elemento más pequeño que el elemento base y luego ejecutaráarr[left]=arr[right]Debido a que la izquierda no se ha movido en este momento, sigue siendo el pivote, pero el pivote lo hemos guardado usando la tecla.

3. ¿Por qué arr[right]>=key?>¿No es posible?

Mayor o igual a es principalmente para procesamiento重复元素问题
Por ejemplo, hay una matriz[6,6,6,6,6]Si es >, el puntero derecho no se moverá, y el puntero izquierdo tampoco se moverá, y quedará atrapado en un bucle infinito.

4. ¿Por qué se llama método de excavación de pozos?

Cuando el puntero r encuentra el primeroarr[r] = arr[l]En este momento, la posición l está en blanco, formando un hoyo.

3. Optimización de clasificación rápida

Hay dos direcciones principales de optimización:

Se puede demostrar que la selección del valor de referencia pivote es que cuando el valor de referencia se selecciona aleatoriamente, la complejidad temporal de la clasificación rápida se acercaO(N*logN), es decir, la mejor complejidad temporal.
Procesamiento de elementos repetidos: si hay una gran cantidad de elementos repetidos dentro del intervalo, la versión anterior del algoritmo de clasificación rápida repetirá los mismos elementos varias veces para reducir operaciones redundantes;数组分三块Al mismo tiempo, si encuentra casos de prueba especiales (matriz secuencial o matriz inversa), la complejidad del tiempo se degradará aO(N^2)

Primero, basado en una pregunta (ordenar por color) entender lo que es数组分三块
analizar

Insertar descripción de la imagen aquí
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

Avisol,r的起始位置, el primer elemento y el último elemento pertenecen a未处理状态, entonces `l, r no puede apuntar a estos dos elementos y debe estar fuera del intervalo
La llamada matriz se divide en tres partes, lo que significa usar三个指针去分别维护四个区间, uno de los intervalos es未处理区间, A medida que el puntero cur continúa moviéndose, se procesan todos los intervalos y, finalmente, solo quedan tres intervalos.

Aplicar las ideas anteriores a快速排序的parttion中, el resultado final se divide en tres intervalos
Insertar descripción de la imagen aquí
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

Insertar descripción de la imagen aquí
2. Seleccione aleatoriamente el valor base
Seleccione aleatoriamente el valor base usando números aleatorios

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

1
2
3

Código completo mejorado:

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

Insertar descripción de la imagen aquí

La eficiencia mejoró significativamente

4. Algoritmo de selección rápida

El algoritmo de selección rápida es基于快速排序优化版本Una complejidad temporal deO(N)El algoritmo de selección, el escenario de uso es第K大/前K大cuestiones de elección como

01.El Késimo elemento más grande de la matriz.
Enlace: https://leetcode.cn/problems/kth-largest-element-in-an-array/
analizar

La solución de la fuerza bruta es utilizarla directamente.sortOrdenar y luego regresar al K-ésimo mayor
complejidad del tiempo:O(N*logN)
Complejidad espacial:O(logN)Llamadas a pila generadas por recursividad

A continuación, se utiliza un algoritmo de selección rápida para implementarO(N)La complejidad temporal de
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

La idea del algoritmo de selección rápida es muy similar a la de clasificación rápida. La diferencia es que el algoritmo de selección rápida solo repite una parte del intervalo de cada resultado de partición, en lugar de repetir todo el intervalo como la clasificación rápida. Se reduce la complejidad del tiempo del algoritmo de selección rápida.O(N)

Compartir tecnología