java - 不用递归如何实现快速排序？

Question

今天想到一个问题，我记得《剑指offer》这本书里面说过：递归都可以转换成循环。那么怎么用循环来实现快速排序，我迄今为止看到的所有快速排序都是用的递归，于我试着写，想了半个小时居然一点头绪都没有。

有哪位大大能够写循环实现的，想开开眼界

阿神 · Answer

用棧儲存，對著改就好了

function qsort_with_loop(arr) {
  let stack = [];

  stack.push([0, arr.length - 1]);

  while (stack.length) {
    let _ = stack.pop();
    let i = l = _[0];
    let j = r = _[1];
    let mid = arr[(i + j) >> 1];

    do {
      while (arr[i] < mid) ++i;
      while (arr[j] > mid) --j;
      if (i <= j) {
        let t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
        ++i;
        --j;
      }
    } while (i <= j);

    if (i < r) stack.push([i, r]);
    if (l < j) stack.push([l, j]);
  }
}