ソートアルゴリズムにおけるC++の再帰関数の応用?

C のソート アルゴリズムにおける再帰関数の適用 再帰関数によって実装された挿入ソートおよびマージ ソート アルゴリズムは、複雑な問題をより小さなサブ問題に分解し、再帰呼び出しを通じてそれらを効率的に解決できます。挿入ソート: 要素を 1 つずつ挿入して配列をソートします。マージソート: 分割統治し、配列を分割してサブ配列を再帰的にソートし、最後にソートされたサブ配列をマージします。

#C 並べ替えアルゴリズムにおける再帰関数の適用

再帰関数は、そのシンプルさと効率性のため、プログラマの間で非常に人気があります。並べ替えアルゴリズムでは、再帰関数は複雑な問題を簡単に処理し、効率的な解決策を提供できます。この記事では、並べ替えアルゴリズムにおける C の再帰関数の応用を検討し、それらがどのように機能するかを例とともに説明します。

挿入ソート

挿入ソートは、隣接する要素を比較し、それらを順番に挿入することによって配列をソートする単純なソート アルゴリズムです。再帰関数を使用して、効率的な挿入ソート アルゴリズムを実装できます。

// 递归插入排序函数
void insertionSort(int arr[], int n) {
  // 基线条件：数组只有一个元素时，不需要排序
  if (n <= 1) {
    return;
  }

  // 递归调用：对子数组执行插入排序
  insertionSort(arr, n - 1);

  // 插入最后一个元素到排序好的子数组中
  int last = arr[n - 1];
  int j = n - 2;

  while (j >= 0 && arr[j] > last) {
    arr[j + 1] = arr[j];
    j--;
  }

  arr[j + 1] = last;
}

マージ ソート

マージ ソートは、配列を分割して分割する分割統治型のソート アルゴリズムです。より小さいサブ配列を分割し、それらをソートされた配列にマージする前に再帰的にソートします。以下は、再帰を使用して実装されたマージ ソート アルゴリズムです。

// 递归归并排序函数
void mergeSort(int arr[], int l, int r) {
  // 基线条件：数组只有一个元素时，直接返回
  if (l >= r) {
    return;
  }

  // 计算数组中点
  int m = l + (r - l) / 2;

  // 递归调用：对数组的左半部分和右半部分执行归并排序
  mergeSort(arr, l, m);
  mergeSort(arr, m + 1, r);

  // 合并两个排序好的子数组
  merge(arr, l, m, r);
}

// 合并两个排序好的子数组的辅助函数
void merge(int arr[], int l, int m, int r) {
  // 创建一个临时数组，用于合并两个子数组
  int temp[r - l + 1];

  int i = l;
  int j = m + 1;
  int k = 0;

  // 循环比较两个子数组的元素，将较小的元素添加到临时数组中
  while (i <= m && j <= r) {
    if (arr[i] <= arr[j]) {
      temp[k++] = arr[i++];
    } else {
      temp[k++] = arr[j++];
    }
  }

  // 将剩余的元素添加到临时数组中
  while (i <= m) {
    temp[k++] = arr[i++];
  }

  while (j <= r) {
    temp[k++] = arr[j++];
  }

  // 将临时数组复制回原始数组
  for (int i = l; i <= r; i++) {
    arr[i] = temp[i - l];
  }
}

実用的なケース

ソート アルゴリズムでの再帰関数の適用を示すために、次の例を考えてみましょう。 ##

int main() {
  // 创建一个无序数组
  int arr[] = {64, 34, 25, 12, 22, 11, 90};
  int n = sizeof(arr) / sizeof(arr[0]);

  // 使用插入排序对数组进行排序
  insertionSort(arr, n);

  // 打印排序后的数组
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;

  // 使用归并排序对数组进行排序
  mergeSort(arr, 0, n - 1);

  // 打印排序后的数组
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;

  return 0;
}

出力:

11 12 22 25 34 64 90 
11 12 22 25 34 64 90

出力に示されているように、再帰関数は、挿入ソート アルゴリズムとマージ ソート アルゴリズムを使用して配列をソートするために使用されています。

以上がソートアルゴリズムにおけるC++の再帰関数の応用?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。