import java.util.Arrays;
import java.util.Stack;
public class Main {
/**
* 采用非递归的方法，首先要想到栈的使用，通过阅读递归调用部分的代码，思考如何用栈来代替。
* 递归调用的核心代码是 temp = partition(a, low, high);
* 每次循环都必须包含这句核心代码，可以想到，如果要对该行代码实现循环，
* 只能对low和high采取操作，所以我们在栈中压入low和high，
* 每个循环弹出一对low和high，用于核心代码的实现，
* 当栈空后就说明没有需要排序的部分了，结束循环。
*
*/
private static void nonRec_quickSort(int[] arr) {
if (arr.length <= 1) {
return;
}
nonRec_quickSort(arr,0,arr.length - 1);
}
// start和end为前闭后闭
private static void nonRec_quickSort(int[] a, int start, int end) {
// 用栈模拟
Stack<Integer> stack = new Stack<>();
if (start < end) {
stack.push(end);
stack.push(start);
while (!stack.isEmpty()) {
int l = stack.pop();
int r = stack.pop();
int index = partition(a, l, r);
if (l < index - 1) {
stack.push(index - 1);
stack.push(l);
}
if (r > index + 1) {
stack.push(r);
stack.push(index + 1);
}
}
}
System.out.println(Arrays.toString(a));
}
private static int partition(int[] a, int start, int end) {
int temp = a[start];
while (start < end) {
while (start < end && a[end] >= temp)
end--;
a[start] = a[end];
while (start < end && a[start] <= temp)
start++;
a[end] = a[start];
}
a[start] = temp;
return start;
}
//for test
public static void main(String[] args) {
int[] arr = {3,2,5,8,4,7,6,9};
nonRec_quickSort(arr);
System.out.println(Arrays.toString(arr));
}
}
| 
转播
