Application de la fonction récursive C++ dans l'algorithme de tri ?-C++-php.cn

Application de la fonction récursive C++ dans l'algorithme de tri ?

WBOY

Libérer： 2024-04-17 11:06:02

original

344 Les gens l'ont consulté

C++ 中递归函数在排序算法中的应用通过递归函数实现的插入排序和归并排序算法，可以将复杂的问题分解为更小的子问题，并通过递归调用高效地解决。插入排序：通过逐个插入元素，将数组有序化。归并排序：分而治之，将数组拆分并递归排序子数组，最后将排序后的子数组合并。

C++ 递归函数在排序算法中的应用？

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;
}

Copier après la connexion

归并排序

归并排序是一种分而治之的排序算法，它将数组拆分成更小的子数组，并递归地对它们进行排序，然后再将它们合并成一个排序好的数组。以下是用递归实现的归并排序算法：

// 递归归并排序函数
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];
  }
}

Copier après la connexion

实战案例

为了展示递归函数在排序算法中的应用，考虑以下示例：

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;
}

Copier après la connexion

输出：

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

Copier après la connexion

如输出所示，递归函数已被用于使用插入排序和归并排序算法对数组进行排序。

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!