算法之快速排序 - 翁先森的博客

快速排序就是:

选取基准元素
比基准元素小的元素放到左边，大的放右边
在左右子数组中重复步骤一二，直到数组只剩下一个元素
向上逐级合并数组

基本实现#

1
function quickSort(arr = []) {
2
  if (arr.length <= 1) return arr;
3

4
  const middleIdx = Math.floor(arr.length / 2) || 0;
5

6
  const middle = arr.splice(middleIdx, 1)[0];
7

8
  const leftArr = [];
9

10
  const rightArr = [];
11

12
  arr.forEach((item) => {
13
    item > middle ? rightArr.push(item) : leftArr.push(item);
14
  });
15

16
  return [...quickSort(leftArr), middle, ...quickSort(rightArr)];
17
}
18

19
console.log(quickSort([2, 9, 7, 8, 1, 4, 6, 5]));

优化（重写算了，但思路一样）#

上边这个快排只是找找感觉，我们不能这样写快排，如果每次都开两个数组，会消耗很多内存空间，数据量大时可能造成内存溢出，我们要避免开新的内存空间，即原地完成排序

我们可以用元素交换来取代开新数组，在每一次分区的时候直接在原数组上交换元素，将小于基准数的元素挪到数组开头，以[5,1,4,2,3]为例：

我们定义一个pos指针, 标识等待置换的元素的位置, 然后逐一遍历数组元素, 遇到比基准数小的就和arr[pos]交换位置, 然后pos++

1
function quickSortPro(arr) {
2
  function swap(first, next) {
3
    let temp = arr[first];
4
    arr[first] = arr[next];
5
    arr[next] = temp;
6
  }
7
  function quicker(left, right) {
8
    if (left < right) {
9
      const last = arr[right];
10
      let pos = left - 1;
11
      for (let i = left; i <= right; i++) {
12
        if (arr[i] <= last) {
13
          pos++;
14
          swap(i, pos);
15
        }
16
      }
17
      quicker(left, pos - 1);
18
      quicker(pos + 1, right);
19
    }
20
  }
21
  quicker(0, arr.length - 1);
22
  return arr;
23
}

这个交换的过程还是需要一些时间理解消化的，详细分析可以看这篇：js算法-快速排序(Quicksort)