Anwendung der rekursiven C++-Funktion im Sortieralgorithmus?

Die Anwendung rekursiver Funktionen in Sortieralgorithmen in C++, die durch rekursive Funktionen implementiert werden, können komplexe Probleme in kleinere Teilprobleme zerlegen und diese durch rekursive Aufrufe effizient lösen. Einfügungssortierung: Sortiert ein Array, indem Elemente einzeln eingefügt werden. Sortierung zusammenführen: Teilen und erobern, das Array aufteilen und die Unterarrays rekursiv sortieren und schließlich die sortierten Unterarrays zusammenführen.

Anwendung rekursiver C++-Funktionen in Sortieralgorithmen

Rekursive Funktionen sind aufgrund ihrer Einfachheit und Effizienz bei Programmierern sehr beliebt. In Sortieralgorithmen können rekursive Funktionen komplexe Probleme problemlos bewältigen und effiziente Lösungen bereitstellen. In diesem Artikel wird die Anwendung rekursiver Funktionen in Sortieralgorithmen in C++ untersucht und anhand von Beispielen veranschaulicht, wie sie funktionieren.

Insertion Sort

Insertion Sort ist ein einfacher Sortieralgorithmus, der ein Array sortiert, indem er benachbarte Elemente vergleicht und sie der Reihe nach einfügt. Ein effizienter Sortieralgorithmus für Einfügungen kann mit rekursiven Funktionen implementiert werden:

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

Merge sort

Merge sort ist ein Divide-and-Conquer-Sortieralgorithmus, der ein Array in kleinere Unterarrays aufteilt und diese rekursiv sortiert. Sortiert sie und führt sie dann zu einem sortierten zusammen Array. Das Folgende ist der mit Rekursion implementierte Zusammenführungssortierungsalgorithmus:

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

Praktischer Fall

Um die Anwendung rekursiver Funktionen in Sortieralgorithmen zu demonstrieren, betrachten Sie das folgende Beispiel:

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

Ausgabe:

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

Wie die Ausgabe zeigt, ist die Die rekursive Funktion wird zum Sortieren von Arrays mithilfe von Einfügungssortierungs- und Zusammenführungssortierungsalgorithmen verwendet.

Das obige ist der detaillierte Inhalt vonAnwendung der rekursiven C++-Funktion im Sortieralgorithmus?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!