快速排序java递归实现和遍历实现
时间: 2024-06-19 10:00:33 浏览: 11
快速排序是一种高效的排序算法,它基于分治策略,通过一趟排序将待排记录分隔成独立的两部分,其中一部分的所有数据都比另一部分小,然后分别对这两部分继续进行排序,直到整个序列有序。在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);
}
// 其他辅助方法...
}
```