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

WBOY
Lepaskan: 2024-04-19 13:21:02
asal
457 orang telah melayarinya

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++ 递归函数在分治算法中的应用?

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;
}
Salin selepas log masuk

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);
Salin selepas log masuk

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!

sumber:php.cn
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan