【Java】快速排序的非递归实现

　　快速排序⼀般采⽤递归⽅法（详见），但递归⽅法⼀般都可以⽤循环代替。本⽂实现了java版的⾮递归快速排序。更多：

思路分析

　　采⽤⾮递归的⽅法，⾸先要想到栈的使⽤，通过阅读递归调⽤部分的代码，思考如何⽤栈来代替。递归调⽤的核⼼代码是 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;

/** *

* @Description 快速排序的递归与⾮递归实现 *

* @author yongh

* @date 2018年9⽉14⽇ 下午2:39:00 */

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); } } }

/**

* 对数组a中下标从low到high的元素，选取基准元素pivotKey， * 根据与基准⽐较的⼤⼩，将各个元素排到基准元素的两端。 * 返回值为最后基准元素的位置 */

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

收获

　　递归改为⾮递归，联想到栈的使⽤，根据对核⼼代码的循环，确定栈中存储什么数据。

更多：