快速排序的思路与方法

发表于 | 更新于: | 分类于 ，
字数统计: 484 | 阅读时长 ≈ 1

快速排序算法的思路与实现(js 语言)

D&C(divide and conquer) 分而治之

d&c 是一种递归式解决问题的方法(思路)，使用 d&c 解决问题分为两个步骤:1. 找出基线条件(不再递归的条件),这种条件应该尽可能的简单。 2. 不断将问题分解(或者说缩小规模)，直到符合基线条件

逻辑

如果一个数组是已经排好序的数组，那个在这个数组中任选一个元素，元素左边的元素将会小于等于该元素，元素所有右边的元素将会大于等于该元素。

我们依据该元素，可以对一个无序数组做如下操作。任选一个元素，循环该无需数组，声明两个数组变量，一个是 less,一个是 greater,我们把小于该元素的数放入 less 数组中，把大于该元素放入 greater 中，那个便满足了以上的逻辑。接下来，我们再从 less 数组中选取一个元素，执行如上操作，使得 less 数组又分为两组，一组比选中元素小，一组比选中元素大。对 greater 数组也同样操作。这样下来，最后我们得到的就是一个有序的数组。

步骤

  1. 找基准值(pivot)
  2. 分区(partitioning):找出比基准值以及比基准值大的元素 => 数组划分为:一个小于基准值的子数组,基准值,一个大于基准值的子数组
  3. 递归

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function quickSort(arr) {
  if (arr.length < 2) {
    return arr;
  } else {
    const pivot = arr.splice(Math.floor(arr.length / 2), 1)[0];
    let less = [],
      greater = [];
    for (let i = 0; i < arr.length; i++) {
      if (arr[i] <= pivot) {
        less.push(arr[i]);
      } else {
        greater.push(arr[i]);
      }
    }
    return quickSort(less).concat([pivot], quickSort(greater)); //  结果将存储在这里
  }
}
console.log(JSON.stringify(quickSort([3, 5, 1, 4])));
0%