算法实现: 快速排序 (quicksort)

[lewenweijia]

关键: pivot(基点), 分区算法(partition)

[lewenweijia]

其他

mergeSort, 可贵的是merge算法啊 quickSort, 可贵的是partition算法的啊 partition算法实现思路: 1. 快慢指针 2. 对撞指针

1. 原地快排
2. 原地归并?

并行归并排序, 并行快速排序

[lewenweijia]

function quickSort(arr) {
  function _quickSort(left, right) {
    // termination case;
    if (left >= right) return;

    const pIdx = partition(left, right);
    _quickSort(left, pIdx - 1);
    _quickSort(pIdx + 1, right);
  }

  function partition(left, right) {
    const pVal = arr[right];

  // 快慢指针
    let slow = left;
    for (let fast = left; fast < right; fast++) {
      if (arr[fast] < pVal) {
        [arr[slow], arr[fast]] = [arr[fast], arr[slow]];
        slow++;
      }
    }

    [arr[slow], arr[right]] = [arr[right], arr[slow]];

    return i;
  }

  _quickSort(0, arr.length - 1);

  return arr;
}

console.log(quickSort([3, 7, 2, 8, 2, 782, 7, 29, 1, 3, 0, 34]));