Application of C++ recursive function in sorting algorithm?

The application of recursive functions in sorting algorithms in C The insertion sort and merge sort algorithms implemented through recursive functions can decompose complex problems into smaller sub-problems and solve them efficiently through recursive calls. Insertion sort: Sorts an array by inserting elements one by one. Merge sort: Divide and conquer, split the array and recursively sort the sub-arrays, and finally merge the sorted sub-arrays.

C Application of recursive functions in sorting algorithms

Recursive functions are very popular among programmers because of their simplicity and efficiency. In sorting algorithms, recursive functions can easily handle complex problems and provide efficient solutions. This article will explore the application of recursive functions in C in sorting algorithms and illustrate how they work with examples.

Insertion sort

Insertion sort is a simple sorting algorithm that sorts an array by comparing adjacent elements and inserting them in order. You can use recursive functions to implement an efficient insertion sort algorithm:

// 递归插入排序函数
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 is a divide-and-conquer sorting algorithm that splits an array into smaller subarrays and recursively sort them before merging them into a sorted array. The following is a merge sort algorithm implemented using recursion:

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

Practical case

To demonstrate the application of recursive functions in a sorting algorithm, consider the following example:

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 shown in the output, the recursive function has been used to sort the array using insertion sort and merge sort algorithms.

The above is the detailed content of Application of C++ recursive function in sorting algorithm?. For more information, please follow other related articles on the PHP Chinese website!