分割統治アルゴリズムにおける C++ 再帰関数の応用?

分割統治アルゴリズムは、大きな問題を小さなサブ問題に分解します。C 再帰関数は、基本要素を選択し、配列を基本要素の 2 つの側面に分割します。 2 つの部分を再帰的にソートし、ソートされた部分をマージします。

C 分割統治アルゴリズムにおける再帰関数の適用

分割統治アルゴリズムは、次のような手法です。大きな問題をサブ問題の小さな戦略に分解し、サブ問題を再帰的に解決します。 C の再帰関数は、理解しやすくデバッグしやすいコードを作成できるため、分割統治アルゴリズムの実装に最適です。

クイック ソートのケース スタディ

クイック ソートは、最も一般的な分割統治アルゴリズムの 1 つです。次の手順に従って、順序なし配列を並べ替えます。

1. 基本要素を選択します。
2. 配列内の要素を、基本要素より小さい要素と基本要素より大きい要素の 2 つの部分に分割します。
3. これら 2 つの部分を再帰的に並べ替えます。
4. 並べ替えた 2 つの部分をマージして元の配列に戻します。

次に、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 中国語 Web サイトの他の関連記事を参照してください。