迭代版 Quicksort 算法

February 10, 2019

递归版的 Quicksort 算法:

function partition(arr, from, to) {
  const p = Math.floor((to - from) * Math.random() + from);

  [arr[to - 1], arr[p]] = [arr[p], arr[to - 1]]
  let l = 0;
  for (let i = 0; i < to - 1; i++) {
    if (arr[i] <= arr[to - 1]) {
      [arr[l], arr[i]] = [arr[i], arr[l]]
      l++;
    }
  }
  [arr[to - 1], arr[l]] = [arr[l], arr[to - 1]]

  return l;
}

function _quickSort(arr, from, to) {
  if (to - from < 2) return;
  
  const l = partition(arr, from, to);
  _quickSort(arr, from, l);
  _quickSort(arr, l+1, to);
}

function quickSort(arr) {
  _quickSort(arr, 0, arr.length);
}

这个递归形式类似于二叉树的先序遍历。

如上示意图,从根节点出发往节点的上面分支走,沿途访问的过程中进行节点访问(在此处意味着计算 partition 函数,然后得到节点的上下分支),并将下分支顶点入栈。当上分支消失时,栈顶即为接下来最“上面”的节点,访问它,然后按照同样的方式展开它的子节点访问。

节点 SortNode 以及从该节点获得子分支:

function SortNode(from, to) {
  this.from = from;
  this.to = to;
}
SortNode.prototype.getChildren = function(l) {
  return [new SortNode(this.from, l), new SortNode(l+1, this.to)];
}
SortNode.prototype.isValid = function() {
  return (this.to - this.from >= 2);
}

迭代版算法如下,

function quickSort(arr) {
  const stack = [];
  let curr = new SortNode(0, arr.length);
  while (true) {
    while (curr.isValid()) {
      const l = partition(arr, curr.from, curr.to);
      const [upChild, downChild] = curr.getChildren(l);
      curr = upChild;
      stack.push(downChild);
    }
    if (stack.length === 0) {
      break;
    }
    curr = stack.pop();
  }
}