快速排序一般采用遞歸方法(詳見
思路分析
采用非遞歸的方法，首先要想到棧的使用，通過閱讀遞歸調用部分的代碼，思考如何用棧來代替。遞歸調用的核心代碼是 pivot = partition(a, low, high); 每次循環都必須包含這句核心代碼，可以想到，如果要對該行代碼實作循環，隻能對low和high采取操作，是以我們在棧中壓入low和high，每個循環彈出一對low和high，用于核心代碼的實作，當棧空後就說明沒有需要排序的部分了，結束循環。
下面是遞歸代碼和根據遞歸代碼修改成的非遞歸代碼。
遞歸部分代碼：
public void qSort(int[] a, int low, int high) {
int pivot;
if (low >= high)
return;
//原始遞歸操作
// pivot = partition(a, low, high); // 将數列一分為二
// qSort(a, low, pivot - 1); // 對低子表排序
// qSort(a, pivot + 1, high); // 對高子表排序
// 優化遞歸操作
while (low < high) {
pivot = partition(a, low, high); // 将數列一分為二
qSort(a, low, pivot - 1); // 對低子表排序
low = pivot + 1;
}
}
修改成的非遞歸代碼：
public void qSort2(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);
}
}
}
注意點：棧彈出的順序與壓入的順序相反，要小心棧的壓入與彈出操作。
完整Java代碼
(含測試代碼)
import java.util.Arrays;
import java.util.Stack;
public class QuickSort {
public void quickSort(int[] a) {
if (a == null)
return;
qSort(a, 0, a.length - 1);
}
public void qSort(int[] a, int low, int high) {
int pivot;
if (low >= high)
return;
//原始遞歸操作
// pivot = partition(a, low, high); // 将數列一分為二
// qSort(a, low, pivot - 1); // 對低子表排序
// qSort(a, pivot + 1, high); // 對高子表排序
// 優化遞歸操作
while (low < high) {
pivot = partition(a, low, high); // 将數列一分為二
qSort(a, low, pivot - 1); // 對低子表排序
low = pivot + 1;
}
}
public void quickSort2(int[] a) {
if (a == null)
return;
qSort2(a, 0, a.length - 1);
}
public void qSort2(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 int partition(int[] a, int low, int high) {
// 三數取中,将中間元素放在第一個位置
if (a[low] > a[high])
swap(a, low, high);
if (a[(low + high) / 2] > a[high])
swap(a, (low + high) / 2, high);
if (a[low] < a[(low + high) / 2])
swap(a, (low + high) / 2, low);
int pivotKey = a[low]; // 用第一個元素作為基準元素
while (low < high) { // 兩側交替向中間掃描
while (low < high && a[high] >= pivotKey)
high--;
a[low] = a[high];
// swap(a, low, high); //比基準小的元素放到低端
while (low < high && a[low] <= pivotKey)
low++;
a[high] = a[low];
// swap(a, low, high); //比基準大的元素放到高端
}
a[low] = pivotKey; // 在中間位置放回基準值
return low; // 傳回基準元素所在位置
}
public void swap(int[] a, int i, int j) {
int temp;
temp = a[j];
a[j] = a[i];
a[i] = temp;
}
// =========測試代碼=======
//測試的為非遞歸方法quickSort2()
public void test1() {
int[] a = null;
quickSort2(a);
System.out.println(Arrays.toString(a));
}
public void test2() {
int[] a = {};
quickSort2(a);
System.out.println(Arrays.toString(a));
}
public void test3() {
int[] a = { 1 };
quickSort2(a);
System.out.println(Arrays.toString(a));
}
public void test4() {
int[] a = { 3, 3, 3, 3, 3 };
quickSort2(a);
System.out.println(Arrays.toString(a));
}
public void test5() {
int[] a = { -3, 6, 3, 1, 3, 7, 5, 6, 2 };
quickSort2(a);
System.out.println(Arrays.toString(a));
}
public static void main(String[] args) {
QuickSort demo = new QuickSort();
demo.test1();
demo.test2();
demo.test3();
demo.test4();
demo.test5();
}
}
null[]
[1]
[3, 3, 3, 3, 3]
[-3, 1, 2, 3, 3, 5, 6, 6, 7]
QuickSort
收獲
遞歸改為非遞歸，聯想到棧的使用，根據對核心代碼的循環，确定棧中存儲什麼資料。