用c++写一个递归的快速排序
时间: 2023-09-05 22:05:28 浏览: 61
### 回答1:
很高兴能够与你交谈!快速排序是一种基于比较的排序算法,它可以用递归的方式来实现。C语言中,可以通过编写一个函数来实现快速排序,该函数的比较操作可以使用两个参数,一个是待排序的数组,另一个是元素的数量。函数进行递归调用,每次调用时,它会通过比较将数组元素分为两组,然后再分别对这两组元素进行排序,最后将排序结果合并。
### 回答2:
快速排序是一种基于比较的排序算法,使用分治的策略。它通过选择一个基准值,将数组分割成两个子数组,然后递归地对这两个子数组进行排序。以下是使用C语言编写的递归快速排序算法的实现:
```c
#include <stdio.h>
// 交换两个元素的值
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) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// 测试例子
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("排序后的数组:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
```
以上代码实现了一个简单的递归快速排序算法。在main函数中,我们定义了一个包含5个元素的整型数组,然后调用quickSort函数对数组进行递归快速排序,并输出排序后的结果。输出结果为:11 12 22 25 64。这证明递归快速排序已成功排序该数组。
### 回答3:
快速排序是一种常用的排序算法,它基于分治法的思想。使用C语言实现递归的快速排序可以按照以下步骤进行:
1. 首先定义一个递归函数`quickSort`,它接受一个整型数组`arr`、待排序元素的起始位置`start`和结束位置`end`作为参数。
2. 在`quickSort`函数中,选择一个基准元素`pivot`,可以选择数组的中间元素。
3. 将数组分为两部分,使得左边的元素都小于等于基准元素,右边的元素都大于基准元素。可以使用两个指针`i`和`j`,分别指向数组的起始和结束位置。
4. 将比基准元素小的元素放到左边,将比基准元素大的元素放到右边,直到`i`和`j`相遇。
5. 将基准元素交换到`i`指针所在的位置。
6. 递归地对左边的子数组和右边的子数组进行快速排序,即调用`quickSort(arr, start, i-1)`和`quickSort(arr, i+1, end)`。
下面是一个示例代码:
```
#include <stdio.h>
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int start, int end) {
int pivot = arr[end];
int i = (start - 1);
for (int j = start; j <= end - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[end]);
return (i + 1);
}
void quickSort(int arr[], int start, int end) {
if (start < end) {
int pivotIndex = partition(arr, start, end);
quickSort(arr, start, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, end);
}
}
int main() {
int arr[] = {8, 3, 2, 7, 1, 5, 4, 6};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
```
运行上述代码,可以得到已排序的数组`1 2 3 4 5 6 7 8`。这就是使用C语言实现的递归快速排序的示例。