java排序递归与递推
时间: 2024-06-12 15:09:59 浏览: 10
Java中的排序算法可以使用递归和递推两种方式实现。递归是一种自我调用的算法,可以将一个大问题分解成多个小问题,然后逐个解决小问题,最终得到大问题的解。递推则是从已知的初始状态开始,通过不断迭代计算得到最终结果。
在Java中,常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序等。这些算法都可以使用递归或递推实现。
以快速排序为例,递归实现代码如下:
```
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
while (left < right) {
while (left < right && arr[right] >= pivot) {
right--;
}
arr[left] = arr[right];
while (left < right && arr[left] <= pivot) {
left++;
}
arr[right] = arr[left];
}
arr[left] = pivot;
return left;
}
```
递推实现代码如下:
```
public static void quickSort(int[] arr) {
Stack<Integer> stack = new Stack<>();
stack.push(0);
stack.push(arr.length - 1);
while (!stack.isEmpty()) {
int right = stack.pop();
int left = stack.pop();
if (left < right) {
int pivot = partition(arr, left, right);
stack.push(left);
stack.push(pivot - 1);
stack.push(pivot + 1);
stack.push(right);
}
}
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
while (left < right) {
while (left < right && arr[right] >= pivot) {
right--;
}
arr[left] = arr[right];
while (left < right && arr[left] <= pivot) {
left++;
}
arr[right] = arr[left];
}
arr[left] = pivot;
return left;
}
```