Application of C++ recursive function in divide-and-conquer algorithm?

The divide-and-conquer algorithm decomposes a large problem into smaller sub-problems. The C recursive function can implement the divide-and-conquer algorithm: select the base element; split the array into two sides of the base element; recursively sort the two parts; merge the sorted parts.

C Application of recursive functions in divide-and-conquer algorithm

The divide-and-conquer algorithm is a method that decomposes large problems into smaller ones. strategies for subproblems and then solving the subproblems recursively. Recursive functions in C are ideal for implementing divide-and-conquer algorithms because it allows writing code that is easy to understand and debug.

Quick Sort Case Study

Quick Sort is one of the most popular divide-and-conquer algorithms. It sorts an unordered array by following these steps:

1. Select a base element.
2. Divide the elements in the array into two parts: elements smaller than the base element and elements larger than the base element.
3. Sort these two parts recursively.
4. Merge the two sorted parts back into the original array.

The following is an example implementation of the quick sort function in C:

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int partitionIndex = partition(arr, low, high);  // 获取分区索引
        
        // 递归地排序两部分
        quickSort(arr, low, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, high);
    }
}

// 分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准
    int i = low - 1;  // 指向最终小于基准的元素的索引
    
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

Using this quick sort function, you can sort an array as follows:

int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);

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