使用递归函数实现快速排序
时间: 2023-07-17 16:05:18 浏览: 50
可以使用以下递归函数实现n的k次方:
def power(n, k):
if k == 0:
return 1
elif k % 2 == 0:
return power(n, k/2) * power(n, k/2)
else:
return n * power(n, k-1)
这个函数首先检查k是否为0,如果是,则返回1。如果k是偶数,则将问题分解为计算n的k/2次方的平方。如果k是奇数,则将问题分解为计算n的k-1次方并乘以n。这个递归过程将一直进行,直到k减少到0,然后返回1。
相关问题
不使用递归方法的快速排序函数 C语言
以下是不使用递归方法的快速排序函数的C语言代码:
```c
#include <stdio.h>
void quickSort(int arr[], int left, int right) {
int stack[right - left + 1]; // 定义一个栈
int top = -1;
stack[++top] = left; // 将左右边界入栈
stack[++top] = right;
while (top >= 0) {
right = stack[top--]; // 弹出右边界
left = stack[top--]; // 弹出左边界
int i = left, j = right, pivot = arr[left]; // 选择第一个元素作为基准元素
while (i < j) {
while (i < j && arr[j] >= pivot) j--; // 从右往左找到第一个小于基准元素的元素
if (i < j) arr[i++] = arr[j]; // 将该元素放到基准元素左边
while (i < j && arr[i] < pivot) i++; // 从左往右找到第一个大于等于基准元素的元素
if (i < j) arr[j--] = arr[i]; // 将该元素放到基准元素右边
}
arr[i] = pivot; // 将基准元素放到正确位置
if (i - 1 > left) { // 如果左边有元素,将左边界和右边界入栈
stack[++top] = left;
stack[++top] = i - 1;
}
if (i + 1 < right) { // 如果右边有元素,将左边界和右边界入栈
stack[++top] = i + 1;
stack[++top] = right;
}
}
}
int main() {
int arr[] = {5, 3, 9, 2, 8, 7, 1, 10, 4, 6};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("排序后的数组:");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
```
该函数使用了一个栈来存储待排序子序列的左右边界。每次从栈中弹出一个左右边界,进行一轮快速排序。如果左边或右边还有元素,将左右边界入栈,继续下一轮排序。由于该算法不使用递归,因此避免了递归调用产生的额外开销,可以提高效率。
快速排序递归函数的边界选择
快速排序递归函数的边界选择是通过选择一个基准值(pivot)来划分待排序序列。基准值的选择可以采用不同的方法,常见的有三种划分方法:Hoare、挖坑法和前后指针法[^2]。
1. Hoare划分方法:选择序列的第一个元素作为基准值,然后从序列的两端开始向中间扫描,直到找到左边大于基准值、右边小于基准值的元素,然后交换这两个元素。重复这个过程直到左右指针相遇,将基准值与相遇位置的元素交换。最后,基准值左边的元素都小于等于基准值,右边的元素都大于等于基准值。然后,递归地对左右两部分进行快速排序。
2. 挖坑法:选择序列的第一个元素作为基准值,然后从序列的右端开始向左扫描,找到第一个小于基准值的元素,将其填入基准值所在的位置。然后,从序列的左端开始向右扫描,找到第一个大于基准值的元素,将其填入上一步空出的位置。重复这个过程直到左右指针相遇,将基准值填入相遇位置。最后,基准值左边的元素都小于等于基准值,右边的元素都大于等于基准值。然后,递归地对左右两部分进行快速排序。
3. 前后指针法:选择序列的第一个元素作为基准值,然后设置两个指针,一个指向序列的左端,一个指向序列的右端。先移动右指针,直到找到一个小于基准值的元素,然后移动左指针,直到找到一个大于基准值的元素,交换这两个元素。重复这个过程直到左右指针相遇,将基准值与相遇位置的元素交换。最后,基准值左边的元素都小于等于基准值,右边的元素都大于等于基准值。然后,递归地对左右两部分进行快速排序。
以上是快速排序递归函数的边界选择的三种常见方法。根据不同的划分方法,基准值的选择和划分过程会有所不同,但最终的目标都是将序列划分为两部分,并递归地对这两部分进行排序。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)