递归算法实现排序问题c++代码
时间: 2024-10-12 17:09:07 浏览: 12
递归排序算法通常用于实现像快速排序、归并排序这样的高效算法。这里是一个使用C++实现的快速排序的例子,它采用递归的方式来划分数组:
```cpp
#include <iostream>
using namespace std;
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
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);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
// pi is partitioning index, arr[p] is now at right place
int pi = partition(arr, low, high);
// Separately sort elements before
// and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Function to print an array
void printArray(int arr[], int size) {
int i;
for (i=0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
}
```
在这个例子中,`quickSort`函数是递归的核心,它不断划分数组,直到每个子数组只有一个元素,递归结束。`partition`函数则负责将数组划分为两部分。
阅读全文