public static void quickSort(int[] arr, int low, int high){ //递归实现 if (arr == null || low < 0 || high <= 0 || low>high) return; int k = partition(arr, low, high); if (k < high){ quickSort(arr, k+1, high); }
if (k > low){ quickSort(arr, low ,k-1); } } public static void quickSortNonRecursion(int[] arr, int low, int high){ //非递归,使用stack保存partition返回值 if (arr == null || low < 0 || high <= 0 || low>high) return; Stack<Integer> temp = new Stack<>(); int i, j; //(注意保存顺序)先将初始状态的左右指针压栈 temp.push(high);//先存右指针 temp.push(low);//再存左指针 while (!temp.empty()) { i = temp.pop();//先弹出左指针 j = temp.pop();//再弹出右指针 if (i < j) { int k = partition(arr, i, j); if (k > i) { temp.push(k - 1);//保存中间变量 temp.push(i); //保存中间变量 } if (j > k) { temp.push(j); temp.push(k + 1); } }