[Tri-Tri rapide]_developdoc

[Tri-Tri rapide]

2024-07-12

Quick Sort est un algorithme de tri efficace basé sur la stratégie diviser pour régner. L'idée principale de cet algorithme de tri est de sélectionner un élément de référence, de diviser le tableau en deux parties, de sorte que les éléments de gauche soient inférieurs ou égaux à l'élément de référence et que les éléments de droite soient supérieurs ou supérieurs. égal à l'élément de référence, puis appliquez récursivement un tri rapide aux deux parties.

Étapes de l'algorithme :

Sélectionnez l'élément de base : Sélectionnez un élément du tableau comme pivot. Habituellement, le premier élément, le dernier élément ou un élément aléatoire est choisi comme base.
Cloison : Réorganisez le tableau de sorte que les éléments plus petits que l'élément de base soient sur le côté gauche de l'élément de base et que les éléments plus grands que l'élément de base soient sur le côté droit. Dans le même temps, l'élément de base se trouve à la position de tri finale.
tri récursif: Triez rapidement les sous-tableaux sur les côtés gauche et droit de l'élément de référence de manière récursive.

Étapes de mise en œuvre :

Voici le code pour implémenter le tri rapide en langage 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

Analyse des codes :

fonction d'échange: Utilisé pour échanger les valeurs de deux éléments dans un tableau.
fonction de partition: Sélectionnez le dernier élément du tableau comme base, divisez le tableau en deux parties et renvoyez l'index de position finale de l'élément de base.
fonction de tri rapide : Algorithme récursif pour implémenter le tri rapide. Dans chaque récursion, la fonction de partition est d'abord utilisée pour partitionner le tableau, puis les deux parties partitionnées sont triées de manière récursive.
fonction printArray: Utilisé pour imprimer les éléments du tableau pour une visualisation facile des résultats du tri.
fonction principale: Testez l'implémentation du tri rapide et imprimez le tableau avant et après le tri.

complexité temporelle :

La complexité temporelle du tri rapide dépend principalement de la complexité temporelle de l'opération de partitionnement et du nombre d'appels récursifs. La complexité temporelle du tri rapide est O(n^2) dans le pire des cas, mais O(n log n) dans le cas moyen, ce qui en fait un algorithme de tri efficace.

Résumer:

Le tri rapide permet un tri efficace grâce à la stratégie diviser pour régner et aux opérations de partitionnement. Il ne nécessite aucun espace de stockage supplémentaire (à l'exception de l'espace de pile pour les appels récursifs) et offre de bonnes performances dans des circonstances moyennes. Par conséquent, le tri rapide est l’un des algorithmes de tri couramment utilisés dans les applications pratiques, particulièrement adapté aux tâches de tri de grands ensembles de données.

Partage de technologie