java非递归快速排序
时间: 2023-10-14 16:29:49 浏览: 44
以下是Java实现的非递归快速排序代码:
```java
import java.util.Stack;
public class NonRecursiveQuickSort {
public static void sort(int[] arr) {
Stack<Integer> stack = new Stack<>();
int low = 0, high = arr.length - 1;
stack.push(low);
stack.push(high);
while (!stack.empty()) {
high = stack.pop();
low = stack.pop();
int pivotIndex = partition(arr, low, high);
if (pivotIndex - 1 > low) {
stack.push(low);
stack.push(pivotIndex - 1);
}
if (pivotIndex + 1 < high) {
stack.push(pivotIndex + 1);
stack.push(high);
}
}
}
private static 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 static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
```
非递归快速排序的主要思想是使用栈来模拟递归调用的过程,每次将待排序区间的左右端点压入栈中,然后弹出栈顶元素,进行分区操作,再将新的左右端点压入栈中,直到栈为空为止。
相关推荐
![](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)