绝大多数的递归逻辑,都可以用栈的方式来代替。每次进入一个新方法,就相当于入栈,每次有方法返回,就相当于出栈。
public class Sort {
public static void QuickSort(int[] arr,int startIndex,int endIndex){
// 用一个集合栈来代替递归的函数栈
Stack<Map<String,Integer>> quickSortStack = new Stack<>();
// 整合数列的起止下标,以哈希的形式入栈
Map rootParam = new HashMap();
rootParam.put("startIndex",startIndex);
rootParam.put("endIndex",endIndex);
quickSortStack.push(rootParam);
// 循环结束条件:栈为空时
while (!quickSortStack.empty()){
// 栈顶元素出栈,得到起止下标
Map<String,Integer> param = quickSortStack.pop();
// 得到基准元素位置
int pivotIndex = partition(arr, param.get("startIndex"),param.get("endIndex"));
// 根据基准元素分成两部分,把每一部分的起止下标入栈
if(param.get("startIndex") < pivotIndex - 1){
Map<String,Integer> leftParam = new HashMap<>();
leftParam.put("startIndex",param.get("startIndex"));
leftParam.put("endIndex",pivotIndex-1);
quickSortStack.push(leftParam);
}
}
}
/**
* 分治(单边循环法)
* @param arr
* @param startIndex
* @param endIndex
* @return
*/
private static int partition(int[] arr, Integer startIndex, Integer endIndex) {
// 取第1个位置(也可以选择随机位置)的元素作为基准元素
int pivot = arr[startIndex];
int mark = startIndex;
for(int i = startIndex+1;i <= endIndex;i++){
if(arr[i] < pivot){
mark++;
int p = arr[i];
arr[i] = arr[mark];
arr[mark] = p;
}
}
arr[startIndex] = arr[mark];
arr[mark] = pivot;
return mark;
}
public static void main(String[] args) {
int[] arr = new int[]{5,8,6,1,7,3,4,9};
QuickSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
}