Quicksort se usa con frecuencia porque su eficiencia de ordenación es mayor entre varios métodos de ordenación con O(N*logN). Además, la idea del quicksort —el método de divide y vencerás— es realmente práctica. Por lo tanto, muchas empresas de software lo incluyen en exámenes escritos y entrevistas, incluidas conocidas empresas de TI como Tencent y Microsoft. También aparece a menudo en exámenes de programación de mayor o menor escala, como el examen de software y el examen de ingreso a posgrado.

=a

Quicksort es un método de ordenación por partición e intercambio propuesto por C.R.A. Hoare en 1962. Utiliza una estrategia de dividir y conquistar, comúnmente llamada método de divide y vencerás (Divide-and-Conquer Method).

La idea básica de este método es:

• 1. Primero toma un número de la secuencia como número pivote.
• 2. Proceso de partición: coloca todos los números mayores que este número a su derecha, y todos los menores o iguales a su izquierda.
• 3. Repite el paso 2 en los intervalos izquierdo y derecho hasta que cada intervalo tenga un solo número.

Aunque el quicksort se llama método de divide y vencerás, estas tres palabras claramente no pueden resumir bien todos los pasos del quicksort. Por lo tanto, he hecho una explicación adicional del quicksort: cavar hoyos y rellenar números + divide y vencerás.

Veamos primero un ejemplo; la definición se dará más abajo (es mejor resumir la definición con tus propias palabras, ya que ayudará a implementar el código).

 

Tomemos un array como ejemplo, y el primer número del intervalo como número pivote.

0	1	2	3	4	5	6	7	8	9
72	6	57	88	60	42	83	73	48	85

Inicialmente, i = 0; j = 9; X = a[i] = 72

Dado que el número en a

Desde j, busca de derecha a izquierda un número menor o igual que X. Cuando j=8, cumple la condición; saca a

 

El array queda así:

0	1	2	3	4	5	6	7	8	9
48	6	57	88	60	42	83	73	88	85

 

i = 3;   j = 7;   X=72

Repite los pasos anteriores: primero busca de derecha a izquierda, luego de izquierda a derecha.

Desde j, busca de derecha a izquierda. Cuando j=5, cumple la condición; saca a

Desde i, busca de izquierda a derecha. Cuando i=5, como i==j, se sale del bucle.

En este momento, i = j = 5, y a

El array queda así:

0	1	2	3	4	5	6	7	8	9
48	6	57	42	60	72	83	73	88	85

Se puede ver que los números antes de a

 

Resumen del método de cavar hoyos y rellenar números:

• 1. i = L; j = R; saca el número pivote formando el primer hoyo a[i].
• 2. j--: busca de derecha a izquierda un número menor que él; al encontrarlo, sácalo y rellena el hoyo anterior a[i].
• 3. i++: busca de izquierda a derecha un número mayor que él; al encontrarlo, sácalo y rellena el hoyo anterior a[j].
• 4. Repite los pasos 2 y 3 hasta que i==j, luego rellena a[i] con el número pivote.

Siguiendo este resumen es muy fácil implementar el código de cavar hoyos y rellenar números:

int AdjustArray(int s[], int l, int r) // Devuelve la posición del número pivote después del ajuste { int i = l, j = r; int x = s[l]; // s[l], es decir s[i], es el primer hoyo while (i < j) { // Busca de derecha a izquierda un número menor que x para rellenar s[i] while(i < j && s[j] >= x) j--; if(i < j) { s[i] = s[j]; // Rellena s[i] con s[j]; s[j] forma un nuevo hoyo i++; } // Busca de izquierda a derecha un número mayor o igual que x para rellenar s[j] while(i < j && s[i] < x) i++; if(i < j) { s[j] = s[i]; // Rellena s[j] con s[i]; s[i] forma un nuevo hoyo j--; } } // Al salir, i es igual a j. Rellena este hoyo con x. s[i] = x; return i; }

Luego escribe el código del método de divide y vencerás:

void quick_sort1(int s[], int l, int r) { if (l < r) { int i = AdjustArray(s, l, r);// Primero usa el método de cavar hoyos y rellenar números para ajustar s[] quick_sort1(s, l, i - 1); // Llamada recursiva quick_sort1(s, i + 1, r); } }

Este código obviamente no es lo suficientemente conciso; reorganizémoslo combinándolo.

// Quicksort void quick_sort(int s[], int l, int r) { if (l < r) { //Swap(s[l], s[(l + r) / 2]); // Intercambia este número del medio con el primer número; ver nota 1 int i = l, j = r, x = s[l]; while (i < j) { while(i < j && s[j] >= x) // Busca de derecha a izquierda el primer número menor que x j--; if(i < j) s[i++] = s[j]; while(i < j && s[i] < x) // Busca de izquierda a derecha el primer número mayor o igual que x i++; if(i < j) s[j--] = s[i]; } s[i] = x; quick_sort(s, l, i - 1); // Llamada recursiva quick_sort(s, i + 1, r); } }

El quicksort tiene muchas versiones mejoradas, como elegir el número pivote aleatoriamente, o usar directamente otro método de ordenación cuando hay pocos datos en el intervalo para reducir la profundidad de la recursión. Los interesados pueden investigar más a fondo.

Nota 1: algunos libros usan el número del medio como pivote. Para lograr esto es muy sencillo: solo intercambia el número del medio con el primer número.

Autor: MoreWindows

Original: https://blog.csdn.net/morewindows/article/details/6684558