정렬 알고리즘에 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;
}

Merge sort

Merge 정렬은 배열을 더 작은 하위 배열로 분할하고 재귀적으로 정렬하는 분할 정복 정렬 알고리즘입니다. 정렬. 다음은 재귀로 구현된 병합 정렬 알고리즘입니다.

// 递归归并排序函数
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 중국어 웹사이트의 기타 관련 기사를 참조하세요!