Penggunaan fungsi rekursif C++ dalam algoritma bahagi-dan-takluk?

Algoritma bahagi-dan-takluk menguraikan masalah besar kepada sub-masalah yang lebih kecil Fungsi rekursif C++ boleh melaksanakan algoritma bahagi-dan-takluk: pilih elemen asas membahagikan tatasusunan kepada dua sisi elemen asas; dua bahagian;

C++ Aplikasi fungsi rekursif dalam algoritma divide-and-conquer

Algoritma bahagi-dan-takluk ialah strategi yang menguraikan masalah besar kepada sub-masalah yang lebih kecil dan kemudian menyelesaikan sub-masalah berulang. Fungsi rekursif dalam C++ sesuai untuk melaksanakan algoritma bahagi dan takluk kerana ia membolehkan menulis kod yang mudah difahami dan nyahpepijat.

Kajian Kes Isih Cepat

Isih Cepat ialah salah satu algoritma bahagi dan takluk yang paling popular. Ia mengisih tatasusunan tidak tertib dengan mengikuti langkah berikut:

1. Pilih elemen asas.
2. Bahagikan unsur dalam tatasusunan kepada dua bahagian: unsur yang lebih kecil daripada unsur asas dan unsur yang lebih besar daripada unsur asas.
3. Isih dua bahagian ini secara rekursif.
4. Gabungkan dua bahagian yang disusun kembali ke tatasusunan asal.

Berikut ialah contoh pelaksanaan fungsi isih pantas dalam C++:

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int partitionIndex = partition(arr, low, high);  // 获取分区索引
        
        // 递归地排序两部分
        quickSort(arr, low, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, high);
    }
}

// 分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准
    int i = low - 1;  // 指向最终小于基准的元素的索引
    
    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;
}

Menggunakan fungsi isih pantas ini, anda boleh mengisih tatasusunan seperti berikut:

int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);

Atas ialah kandungan terperinci Penggunaan fungsi rekursif C++ dalam algoritma bahagi-dan-takluk?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!