Comment utiliser l'algorithme de tri rapide en C++

Comment utiliser l'algorithme de tri rapide en C++

L'algorithme de tri rapide est un algorithme de tri couramment utilisé. Son idée principale est de diviser en continu la séquence à trier en deux sous-séquences plus petites et plus grandes, puis de trier les sous-séquences de manière récursive. , rendant finalement toute la séquence ordonnée. Cet article explique comment utiliser l'algorithme de tri rapide en C++ et fournit des exemples de code spécifiques.

L'idée d'implémentation de l'algorithme de tri rapide est la suivante :

1. Sélectionnez un pivot d'élément de référence, qui peut être n'importe quel élément de la séquence. Habituellement, le premier ou le dernier élément est choisi comme base.
2. Placez les éléments de la séquence qui sont plus petits que le pivot à gauche du pivot, et les éléments qui sont plus grands que le pivot sont placés à droite.
3. Triez rapidement les sous-séquences gauche et droite de manière récursive.

Ce qui suit est un exemple de code utilisant C++ pour implémenter l'algorithme de tri rapide :

#include <iostream>
using namespace std;

// 交换两个元素的值
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);  // i代表小于基准的元素的最右边界
    for (int j = low; j <= high - 1; 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++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "原始数组：";
    printArray(arr, n);
    quickSort(arr, 0, n - 1);
    cout << "排序后的数组：";
    printArray(arr, n);
    return 0;
}

Après avoir exécuté le code ci-dessus, vous obtiendrez le résultat suivant :

原始数组：10 7 8 9 1 5 
排序后的数组：1 5 7 8 9 10 

Ce code implémente l'algorithme de tri rapide, en sélectionnant d'abord le dernier élément comme base, puis utilisez la fonction de partition pour diviser le tableau, en plaçant les éléments plus petits que la ligne de base à gauche et les éléments plus grands que la ligne de base à droite. Ensuite, les sous-tableaux gauche et droit sont triés de manière récursive jusqu'à ce que l'ensemble du tableau soit trié.

Résumé : 
Le tri rapide est un algorithme de tri efficace. Sa complexité temporelle moyenne est O(n log n). Il est relativement simple d'implémenter l'algorithme de tri rapide en utilisant C++. Grâce aux exemples de code ci-dessus, vous pouvez comprendre les principes de base et les méthodes de mise en œuvre de l'algorithme de tri rapide, et vous pouvez également l'utiliser de manière flexible dans des applications pratiques.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!