Principio e implementación del algoritmo de clasificación rápida

La idea básica de la clasificación rápida es seleccionar aleatoriamente un elemento de una matriz (generalmente se selecciona el elemento más a la izquierda) como elemento del eje medio y utilizar el elemento del eje medio como estándar de comparación para el elementos restantes., coloque los elementos más pequeños o iguales que el elemento del eje central a la izquierda del elemento del eje central, y coloque los elementos más grandes que el elemento del eje central a la derecha del elemento del eje central.

Luego tome la posición del elemento del eje central actual como límite, trate la mitad izquierda de la submatriz y la mitad derecha de la submatriz como dos nuevas matrices, repita la operación anterior hasta que se complete el número de elementos en la submatriz es menor que Igual a 1 (porque se debe ordenar una matriz de un elemento).

El siguiente código suele utilizar el método Swap para intercambiar los valores de dos elementos en una matriz. El código es el siguiente

public?static?void?Swap(int[. ] A, int?i, int?j){

int?tmp;

tmp = A[i];

A[i] = A [j];

A[j] = tmp;

Información ampliada:

La idea básica del algoritmo de clasificación rápida es: dividir el número para ordenarse en dos partes: las partes izquierda y derecha, todos los datos en una parte son más pequeños que los datos en la otra parte, y luego divida las dos partes de los datos de la misma manera y repita la operación de división anterior hasta todos los datos a ordenar se vuelven ordenados.

Defina dos variables baja y alta, y establezca baja y alta respectivamente en el elemento inicial y el subíndice del último elemento de la secuencia que se va a ordenar. Por primera vez, los valores de bajo y alto son 0 y n-1 respectivamente, y cada valor posterior está determinado por el subíndice del elemento inicial y el último elemento de la secuencia obtenida por división.

Defina una clave variable y luego divida la matriz A en partes izquierda y derecha según el valor de la clave. Generalmente, el valor de la clave es el primer valor del elemento de la secuencia que se va a ordenar. El primer valor es A[0] y cada valor posterior está determinado por el elemento inicial de la secuencia que se va a dividir.

Comience desde el elemento de la matriz señalado por alto y escanee hacia la izquierda. Mientras escanea, compare los elementos de la matriz subíndices con la clave de valor de referencia divisoria en secuencia hasta que alto no sea mayor que bajo o el primero. Se encuentra uno. Al elemento de la matriz que es menor que la clave del valor base se le asigna el valor al elemento de la matriz señalado por bajo y, al mismo tiempo, bajo se desplaza una posición hacia la derecha.

Si bajo sigue siendo más pequeño que alto, entonces el elemento de la matriz señalado por bajo comienza a escanear hacia la derecha. Mientras se escanea, el valor del elemento de la matriz subíndice bajo se compara con la clave de valor base dividida en secuencia. hasta que bajo no sea menor que alto o encuentre el primer elemento de la matriz que sea mayor que la clave del valor base, luego asigna el valor al elemento de la matriz señalado por alto y se mueve hacia arriba una posición hacia la izquierda.

Repita los pasos (3) (4) hasta que el nivel bajo no sea menor que el nivel alto. En este momento, las partes izquierda y derecha obtenidas después de una división exitosa son A[bajo...pos-1] y A[. pos +1...high], donde el valor del elemento de la matriz correspondiente al subíndice pos es la clave del valor base para la división, por lo que al final de la división, al elemento de la matriz con el subíndice pos se le debe asignar el valor como llave.

Material de referencia: algoritmo de clasificación rápida_Enciclopedia Baidu