快速排序的非递归算法JAVA，使用栈来模拟递归

使用栈来模拟递归，消去qSort中的尾递归
public class stackQSort {
private static int Partition(int[] arr, int start, int end) {
//arr[start]为挖的第一个坑
int key = arr[start];
while (start < end) {
while (arr[end] >= key && end > start)
end–;
arr[start] = arr[end];
while (arr[start] <= key && end > start)
start++;
arr[end] = arr[start];
}
arr[start] = key;
return start;
}
public static void qSort(int[] a, int low, int high) {
int pivot;
if (low >= high)
return;
Stack stack = new Stack();
stack.push(low);
stack.push(high);
while (!stack.empty()) {
// 先弹出high,再弹出low
high = stack.pop();
low = stack.pop();
pivot = Partition(a, low, high);
// 先压low,再压high
if (low < pivot - 1) {
stack.push(low);
stack.push(pivot - 1);
}
if (pivot + 1 < high) {
stack.push(pivot + 1);
stack.push(high);
}
}
}
public static void main (String[] args){
int[] a={6,8,1,71,36,28,46,72,10,9};
qSort(a,0,9);
for(int i=0;i<a.length;i++)
System.out.print(a[i]+" ");

		}

}