[Ordenar-Clasificación rápida]

[Clasificar-Clasificación rápida]

2024-07-12

Quick Sort es un algoritmo de clasificación eficiente basado en la estrategia de divide y vencerás. La idea central de este algoritmo de clasificación es seleccionar un elemento de referencia y dividir la matriz en dos partes, de modo que los elementos de la izquierda sean menores o iguales que el elemento de referencia y los elementos de la derecha sean mayores o iguales. igual al elemento de referencia y luego aplica de forma recursiva la clasificación rápida a las dos partes.

Pasos del algoritmo:

Seleccionar elemento base : seleccione un elemento de la matriz como pivote. Normalmente se elige como base el primer elemento, el último elemento o un elemento aleatorio.
Dividir : Reorganice la matriz de modo que los elementos más pequeños que el elemento base estén en el lado izquierdo del elemento base y los elementos más grandes que el elemento base estén en el lado derecho. Al mismo tiempo, el elemento base se encuentra en la posición final de clasificación.
clasificación recursiva: Ordene rápidamente los subarreglos en los lados izquierdo y derecho del elemento de referencia de forma recursiva.

Pasos de implementación:

El siguiente es el código para implementar la clasificación rápida en lenguaje C:

#include <stdio.h>

// 函数：交换数组中两个元素的值
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 函数：将数组分区，并返回基准元素的位置（索引）
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准
    int i = low - 1;  // 初始化分区索引，比基准元素小的元素会放在左边

    for (int j = low; j < high; j++) {
        // 如果当前元素小于或等于基准元素，则将它交换到分区的左边
        if (arr[j] <= pivot) {
            i++;  // 移动分区索引
            swap(&arr[i], &arr[j]);
        }
    }

    // 最后将基准元素交换到正确的位置
    swap(&arr[i + 1], &arr[high]);
    return i + 1;  // 返回基准元素的位置
}

// 函数：实现快速排序
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 对数组进行分区
        int pi = partition(arr, low, high);

        // 对基准元素左边和右边的子数组进行递归排序
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 函数：打印数组元素
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("n");
}

// 主函数：测试快速排序的实现
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: n");
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    printf("排序后的数组: n");
    printArray(arr, n);
    return 0;
}
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

Análisis de código:

función de intercambio: Se utiliza para intercambiar los valores de dos elementos en una matriz.
función de partición: Seleccione el último elemento de la matriz como base, divida la matriz en dos partes y devuelva el índice de posición final del elemento base.
función de clasificación rápida : Algoritmo recursivo para implementar clasificación rápida. En cada recursividad, la función de partición se utiliza primero para particionar la matriz y luego las dos partes particionadas se ordenan de forma recursiva.
función imprimirmatriz: Se utiliza para imprimir elementos de matriz para visualizar fácilmente los resultados de la clasificación.
función principal: Pruebe la implementación de la clasificación rápida e imprima la matriz antes y después de la clasificación.

complejidad del tiempo:

La complejidad temporal de la clasificación rápida depende principalmente de la complejidad temporal de la operación de partición y del número de llamadas recursivas. La complejidad temporal de la clasificación rápida es O(n^2) en el peor de los casos, pero O(n log n) en el caso promedio, lo que lo convierte en un algoritmo de clasificación eficiente.

Resumir:

La clasificación rápida logra una clasificación eficiente mediante la estrategia de divide y vencerás y las operaciones de partición. No requiere espacio de almacenamiento adicional (excepto espacio de pila para llamadas recursivas) y tiene un buen rendimiento en circunstancias normales. Por lo tanto, la clasificación rápida es uno de los algoritmos de clasificación más utilizados en aplicaciones prácticas, especialmente adecuado para tareas de clasificación de grandes conjuntos de datos.

Compartir tecnología