快速排序的JavaScript实现

发表于 更新于 分类于

基本思想

1 在数据集之中，选择一个元素作为”基准”（pivot）。
2 所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。
3 对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

举个栗子

1
let array = [2, 9, 6, 3, 80, 34, 7, 8];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function quickSort(list) {
  if(list.length <= 1) { return list; }
  let left = [], right = [];
  let pivotIndex = Math.floor(list.length / 2);
  let pivot = list.splice(pivotIndex, 1)[0];
  
  for(let index = 0, len = list.length; index < len; index++) {
    let val = list[index];
    
    if(val <= pivot) {
      left.push(val);
    } else {
      right.push(val);
    }
  }
  
  return [...quickSort(left), pivot, ...quickSort(right)];
}

quickSort函数解构

1
2
3
4
5
6
7
8
9
10
11
12
13
let left = [], right = [];
let pivotIndex = Math.floor(list.length / 2);
let pivot = list.splice(pivotIndex, 1)[0];

for(let index = 0, len = list.length; index < len; index++) {
  let val = list[index];
  
  if(val <= pivot) {
    left.push(val);
  } else {
    right.push(val);
  }
}

这部分逻辑正是对基本思想中的1、2点的实践。

  • 1 找出基准数

1
2
let pivotIndex = Math.floor(list.length / 2);
let pivot = list.splice(pivotIndex, 1)[0];

  • 2 以“基准”二分数组

1
2
3
4
5
6
7
8
9
for(let index = 0, len = list.length; index < len; index++) {
  let val = list[index];
  
  if(val <= pivot) {
    left.push(val);
  } else {
    right.push(val);
  }
}

  • 3 重复1、2点

在栗子中的数组执行一次1、2点实现后，你会发现此时执行后出现三个结果
1）letf = [2];
2）pivot = 3;
3）right = [9, 6, 80, 34, 7, 8];

然后依次组合

1
2
[...left, pivot, ...right]
// [2, 3, 9, 6, 80, 34, 7, 8]

你会发现left只有一个元素，那就没有必要继续对left排序，所以没有必要再排序

1
if(list.length <= 1) { return list; }

然后再看right，并不是有序数组。那要怎么办？继续对right排序，调用quickSort

1
2
quickSort(right)
// [...quickSort(left), pivot, ...quickSort(right)];

而

1
return [...quickSort(left), pivot, ...quickSort(right)];

正是对第3点的实践。