C++ 遞迴函數在分治演算法中的應用？

分治演算法將大問題分解成較小子問題，C 遞歸函數可實現分治演算法：選擇基準元素；分割陣列為基準元素兩側；遞歸排序兩部分；合併已排序部分。

C 遞歸函數在分治演算法中的應用

##分治演算法是一種將大問題分解成較小子問題的策略，然後遞歸地解決子問題。 C 中的遞歸函數非常適合實現分治演算法，因為它允許編寫易於理解和調試的程式碼。

快速排序案例研究

快速排序是最受歡迎的分治演算法之一。它透過以下步驟將一個無序數組排序：

選擇一個基準元素。
1. 將陣列中的元素分為兩部分：比基準元素小的元素和比基準元素大的元素。
2. 遞歸地將這兩部分排序。
3. 將排好序的兩部分合併回原數組。

以下是 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;
}

使用此快速排序函數，您可以透過以下方式對陣列進行排序：

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

以上是C++ 遞迴函數在分治演算法中的應用？的詳細內容。更多資訊請關注PHP中文網其他相關文章！