分割統治アルゴリズムは、大きな問題を小さなサブ問題に分解します。C 再帰関数は、基本要素を選択し、配列を基本要素の 2 つの側面に分割します。 2 つの部分を再帰的にソートし、ソートされた部分をマージします。
C 分割統治アルゴリズムにおける再帰関数の適用
分割統治アルゴリズムは、次のような手法です。大きな問題をサブ問題の小さな戦略に分解し、サブ問題を再帰的に解決します。 C の再帰関数は、理解しやすくデバッグしやすいコードを作成できるため、分割統治アルゴリズムの実装に最適です。
クイック ソートのケース スタディ
クイック ソートは、最も一般的な分割統治アルゴリズムの 1 つです。次の手順に従って、順序なし配列を並べ替えます。
次に、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 サイトの他の関連記事を参照してください。