快速排序js

发表于 | 分类于

今天复习一下经典排序算法中的快速排序

快排的核心思想是分治，把一个问题分解为多个小问题进行解决

需要关注的点：

  • 找到一个pivot基准元素
  • 每次排序都是为了让当前队列中pivot左侧的元素值都比pivot小，pivot右侧的元素值都比pivot大
  • 此次排序完成之后，对pivot左侧的列表和右侧的列表重复进行上面的过程

从上面可以看出来，这其实是一个递归的过程

分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边（即i=1），指向数字6。让哨兵j指向序列的最右边（即=10），指向数字。

首先哨兵j开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵j先出动，这一点非常重要（请自己想一想为什么）。哨兵j一步一步地向左挪动（即j–），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。

现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下：

6 1 2 5 9 3 4 7 10 8

到此，第一次交换结束。接下来开始哨兵j继续向左挪动（再友情提醒，每次必须是哨兵j先出发）。他发现了4（比基准数6要小，满足要求）之后停了下来。哨兵i也继续向右挪动的，他发现了9（比基准数6要大，满足要求）之后停了下来。此时再次进行交换，交换之后的序列如下：

6 1 2 5 4 3 9 7 10 8

第二次交换结束，“探测”继续。哨兵j继续向左挪动，他发现了3（比基准数6要小，满足要求）之后又停了下来。哨兵i继续向右移动，糟啦！此时哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下：

3 1 2 5 4 6 9 7 10 8

到此第一轮“探测”真正结束。此时以基准数6为分界点，6左边的数都小于等于6，6右边的数都大于等于6。回顾一下刚才的过程，其实哨兵j的使命就是要找小于基准数的数，而哨兵i的使命就是要找大于基准数的数，直到i和j碰头为止。

接下来就是要对6左侧和右侧的数组分别循环递归进行上面这个过程，直到某次循环发现数组中只有一个元素

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
function quickSort(arr, left, right) {
  let pivot = left // 基准元素
  let i = left + 1 // 左侧 i 指针
  let j = right // 右侧 j 指针
  if (i >= j) {
    return
  }
  // 右侧 j 指针先往左走，找到第一个小于pivot的元素停止，
  // 左侧 i 指针往右走，找到第一个大于pivot的元素停止
  // 交换 i 和 j
  while (i !== j) {
    while (arr[j] > arr[pivot] && i !== j) {
      j--
    }
    while (arr[i] < arr[pivot] && i !== j) {
      i++
    }
    if (i !== j) {
      swap(arr, i, j)
    }
  }
  // 找到 i 和 j 相遇的点，交换该点和pivot的元素
  swap(arr, pivot, i)
  if (i >= 1) {
    quickSort(arr, left, i - 1) // 对左侧列表进行排序
  }
  if (i <= right - 1) {
    quickSort(arr, i + 1, right) // 对右侧列表进行排序
  }
}

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

let arr = [72, 6, 57, 88, 60, 42, 83, 73, 48, 85]
quickSort(arr, 0, arr.length - 1)
console.log(arr)

/**
 * 时间复杂度 O(nlogn)
 * 计数排序 O(n)
 * 桶排序
 * 基数排序（先排个位数再排十位数）
 * https://www.cnblogs.com/onepixel/articles/7674659.html
 */

为什么说 当基准元素在最左边的时候，循环一定要 j 哨兵从右往左先开始

如果说是 j 先从右往左寻找比 pivot 元素更小的元素，之后 i 再从左往右寻找比 pivot 更大的元素

当一轮排序结束的时候（i = j），这个时候肯定是 i 最后停下来的，它停下来是因为碰到了 j ，那么这个时候，j 指向的元素停下来有两种情况：

  • 要么是因为碰到了 i

    这种情况的话，说明 i 原先指向的元素是 因为比 pivot 大 而跟之前 j 指向的元素进行了交换，也就是说，此时 i 指向的元素比pivot要小，那么这种情况下的交换也是没有问题的

  • 要么是因为碰到了比 pivot 更小的元素

    这种情况下 i 循环碰到了 j 而跳出循环的话，pivot 交换是没有问题的，它跟位置 j 的元素交换之后，这个元素会被换到pivot的左侧，比pivot更小

但是如果是从左边先开始遍历的话，当 i 和 j 相遇的时候，是 j 最后停下来的，它停下来是因为碰到了 i，而 i 停下来也有两种情况

  • 要么是因为 i 碰到了比pivot 更大的元素

    这种情况下，i 原本是想要跟 一个小于pivot的元素进行交换，但是因为没有这样的元素了，它只能跟 pivot进行交换，这个时候，就出现了pivot左侧的元素比pivot要大的情况

  • 要么是因为 i 碰到了 j

    这种情况，说明上一次 j 停下的位置上的元素是比 pivot 更大的（经过上一轮的交换之后），这个时候把 j 位置的元素跟 pivot 进行交换，由于pivot是在最左侧的，那么就会出现pivot左侧的元素比pivot还要大的情况，也是错误的

所以说，从左边开始遍历的话是会出问题的

所以如果选择某个边界作为pivot元素的话，遍历要从另一边首先开始

比较复杂，可以看一下下面的例子，能举得出反例也是可以的

还是旧的例子

不过我们是从 i 向右走开始

前面几步的 i , j 换位没出现什么问题，图片就不放出来了，下面放了张会出现问题的步骤的图

i（4）开始向右走，i 希望寻找一个比基准数6大的数，i 走到 3 时，不满足，继续走到 9 ，这时找到了要找的数。

然后到 j（9） ，因为 i 和 j 的位置重合了， 所以 j 没有动， i ==j 的位置和基准数6的位置交换

| 9 1 2 5 4 3 6 7 10 8 |

按快排规则，基准数归位后

基准数左边的数都小于等于基准数（6）
基准数右边的数都大于等于基准数（6）

然而，9在最左边，明显左边的数没有都小于等于基准数6,这时就出现了排序错误。

结论：pivot基准元素的选择会影响到 遍历顺序的选择，要从pivot基准元素的反方向那一侧的指针开始遍历