快速排序左递归和右边递归
时间: 2024-06-22 13:01:34 浏览: 7
快速排序是一种高效的排序算法,其基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,然后分别对这两部分记录继续进行排序,以达到整个序列有序。快速排序可以使用递归的方式实现,其中一种常见的递归策略是左递归和右递归。
**左递归**(也称为Lomuto分区):
- 选择数组的第一个元素作为基准值(pivot)。
- 将数组分为两部分,所有小于基准值的元素移到基准值的左边,所有大于或等于基准值的元素移到基准值的右边。
- 选择数组的最后一个元素作为基准值。
- 将数组分为两部分,所有小于基准值的元素移到基准值的左边,所有大于或等于基准值的元素移到基准值的右边。
- 但是,这里基准值右侧的元素会被放置到正确的位置,而不是直接移动,所以需要从左向右扫描数组找到第一个大于或等于基准值的元素,并将其与基准值交换位置,然后递归处理剩余的右侧子数组。
两种方法的核心思路是一样的,都是将问题分解为更小的子问题,但细节上有所不同。左递归更直观,而右递归可能导致代码更简洁,因为它避免了在分割过程中频繁的元素交换。
相关问题
快速排序java递归实现和遍历实现
快速排序是一种高效的排序算法,它基于分治策略,通过一趟排序将待排记录分隔成独立的两部分,其中一部分的所有数据都比另一部分小,然后分别对这两部分继续进行排序,直到整个序列有序。在Java中,快速排序既可以用递归实现,也可以用循环遍历实现。
**递归实现**:
```java
public class QuickSortRecursion {
public void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1); // 对左半部分递归排序
quickSort(arr, pivotIndex + 1, high); // 对右半部分递归排序
}
}
private int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准
int i = (low - 1); // 指针,初始指向左侧
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++; // 如果当前元素小于基准,向右移动指针
swap(arr, i, j);
}
}
swap(arr, i + 1, high); // 将基准放到正确的位置
return i + 1;
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
```
**遍历实现**:
```java
public class QuickSortIteration {
public void quickSort(int[] arr) {
int len = arr.length;
if (len <= 1) return; // 基线条件:长度为1或0的数组已经排序
stackify(arr, 0, len - 1); // 使用栈模拟递归过程
while (!stack.isEmpty()) {
pivotSort(arr, stack.pop(), stack.pop());
}
}
private void stackify(int[] arr, int low, int high) {
while (low < high) {
push(stack, low, high);
while (!stack.isEmpty() && lessThan(arr, stack.peek(0), stack.peek(1))) {
pivotSort(arr, stack.pop(), high);
high--;
}
while (!stack.isEmpty() && lessThan(arr, low, stack.peek(0))) {
pivotSort(arr, low, stack.pop());
low++;
}
}
}
private void pivotSort(int[] arr, int pivotStart, int pivotEnd) {
int pivot = arr[pivotEnd];
int i = pivotStart - 1;
for (int j = pivotStart; j < pivotEnd; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, pivotEnd);
}
// 其他辅助方法...
}
```
快速排序c语言递归实现
快速排序是一种常用的排序算法,它通过递归地将数组分成较小和较大的两个子数组来实现排序。下面是快速排序的C语言递归实现:
```c
#include <stdio.h>
// 交换两个元素的值
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 将数组分成两部分,并返回分割点的索引
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);
}
}
// 打印数组
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr);
printf("原始数组:\n");
printArray(arr, n);
quickSort(arr, 0, n - 1);
printf("排序后的数组:\n");
printArray(arr, n);
return 0;
}
```
这段代码实现了快速排序算法的递归版本。首先定义了一个`swap`函数用于交换两个元素的值。然后定义了`partition`函数,它选择最后一个元素作为基准值,将数组分成两部分,并返回分割点的索引。接下来是`quickSort`函数,它通过递归调用自身来对分割点左右两个子数组进行排序。最后,在`main`函数中测试了快速排序算法。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![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)