Penggunaan fungsi rekursif C++ dalam algoritma pengisihan?

Aplikasi fungsi rekursif dalam algoritma pengisihan dalam C++ Algoritma isihan sisipan dan gabungan yang dilaksanakan melalui fungsi rekursif boleh menguraikan masalah kompleks kepada sub-masalah yang lebih kecil dan menyelesaikannya dengan cekap melalui panggilan rekursif. Isih sisipan: Mengisih tatasusunan dengan memasukkan elemen satu demi satu. Cantumkan isihan: Bahagi dan takluk, bahagikan tatasusunan dan susun sub-tatasusunan secara rekursif, dan akhirnya gabungkan sub-tatasusunan yang diisih.

Aplikasi fungsi rekursif C++ dalam menyusun algoritma

Fungsi rekursif sangat popular di kalangan pengaturcara kerana kesederhanaan dan kecekapannya. Dalam algoritma pengisihan, fungsi rekursif boleh mengendalikan masalah yang kompleks dengan mudah dan menyediakan penyelesaian yang cekap. Artikel ini akan meneroka aplikasi fungsi rekursif dalam menyusun algoritma dalam C++ dan menggambarkan cara ia berfungsi dengan contoh.

Isih Sisipan

Isih Sisipan ialah algoritma pengisihan mudah yang mengisih tatasusunan dengan membandingkan unsur bersebelahan dan memasukkannya mengikut tertib. Algoritma isihan sisipan yang cekap boleh dilaksanakan menggunakan fungsi rekursif:

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

Isih gabung

Isih gabung ialah algoritma isihan bahagi dan takluk yang membahagikan tatasusunan kepada subarray yang lebih kecil dan menyusunnya secara rekursif Isihnya dan kemudian gabungkannya ke dalam satuan. tatasusunan. Berikut ialah algoritma isihan gabungan yang dilaksanakan dengan rekursi:

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

Kes praktikal

Untuk menunjukkan aplikasi fungsi rekursif dalam algoritma pengisihan, pertimbangkan contoh berikut:

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

Output:

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

As output menunjukkan fungsi rekursif telah Digunakan untuk mengisih tatasusunan menggunakan algoritma isihan sisipan dan menggabungkan.

Atas ialah kandungan terperinci Penggunaan fungsi rekursif C++ dalam algoritma pengisihan?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!