动画展示快速排序全过程

Array.prototype.quickSort = async function quickSort(fn) {
  let arr = this;
  let len = arr.length;

  _quickSort(arr, 0, len - 1);

  function _quickSort(arr, left, right) {
    if (left >= right) return;

    let j = partition(arr, left, right);

    _quickSort(arr, left, j - 1);
    _quickSort(arr, j + 1, right);
  }

  function partition(arr, left, right) {
    let v = arr[left];
    let j = left;

    for (let i = left + 1; i <= right; i++) {
      if (fn(v, arr[i]) > 0) {
        swap(arr, i, j + 1);
        j++;
      }
    }

    swap(arr, left, j); // 把 v 放到正确的位置上
    return j;
  }
};

function swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

双路快排

三路快排

作者: 曾小乱

喜欢写点有意思的东西

发表回复

您的电子邮箱地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据