java快速排序非递归版本
时间: 2024-01-07 16:23:40 浏览: 29
快速排序是一种常用的排序算法,它通过选择一个基准元素,将数组分成两部分,一部分小于基准元素,一部分大于基准元素,然后对这两部分分别进行快速排序。非递归版本的快速排序使用栈来模拟递归过程,避免了递归带来的函数调用开销。
以下是Java实现的非递归版本快速排序的代码:
```java
import java.util.Stack;
public class QuickSortNonRecursive {
public static void quickSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
Stack<Integer> stack = new Stack<>();
stack.push(0);
stack.push(arr.length - 1);
while (!stack.isEmpty()) {
int end = stack.pop(); int start = stack.pop();
int pivotIndex = partition(arr, start, end);
if (pivotIndex - 1 > start) {
stack.push(start);
stack.push(pivotIndex - 1);
}
if (pivotIndex + 1 < end) {
stack.push(pivotIndex + 1);
stack.push(end);
}
}
}
private static int partition(int[] arr, int start, int end) {
int pivot = arr[end];
int i = start - 1;
for (int j = start; j < end; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, end);
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
```
使用示例:
```java
public class Main {
public static void main(String[] args) {
int[] arr = {5, 2, 8, 9, 1, 3};
QuickSortNonRecursive.quickSort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
输出结果为:1 2 3 5 8 9