快速排序中我们依旧可以运用到递归的思路

递归思路详见点击文章
https://www.yuque.com/u12173902/lyff6h/udswhi

但是这一次递归的思路略微有些变化，在归并排序中，不再以某某同学作为基准

思路

还是排队，按身高，从矮到高依次排
把左边一半先排好，然后右边一半先排好
然后把左右两边的队伍合并（merge）起来

举例

  1.                                 [12,17,3,18,9,2,6,5]
  2.                               →[12,17,3,18] [9,2,6,5]
  3.                              →[12,17] [3,18] [9,2] [6,5]
  4.                               → 12,17 3,18 9,2 6,5
  5.                                                                  →merge
  6.                               →[12,17] [3,18] [2,9] [5,6]
  7.                                                     →以左半边为例，按顺序左边提一个，右边提一个进行比较，然后merge
  8.                               → 12>3  //取3，留12继续比较 [3]
  9.                                                                 12<18 //取12，留18继续比较 [3,12]
  10.                                                                 18>17 //取17，留18继续比较 [3,12,17]
  11.                                                                 18        //比较结束，18为最大值 [3,12,17,18]
  12.                                                             →[3,12,17,18]
  13.                                                   →那么右半边同理可得
  14.                                   → 2<5
  15.                                                                 5<9
  16.                                                                 9>6
  17.                                                             →[2,5,6,9]
  18.                                                     再一次merge
  19.                                     →[3,12,17,18] [2,5,6,9]
  20.                                                             →[2,3,5,6,9,12,17,18]

你也可以这样理解

  1. merge([12,17],[3,18])
  2. =[3,merge([12,17],[18])]
  3. =[3,12,merge([17],[18])]
  4. ...

但是需要注意的是，要想用这种左右分别提出进行比较的方法，前提是两个数组必须已经排好序了，所以在进行归并时，我们必须先把数组从最小块开始排起。

实际代码

  1. let sort = (numbers) => {
  2.     if (numbers.length === 1) {
  3.         return numbers
  4.     }
  5.     let left = numbers.slice(0, Math.floor(numbers.length / 2))
  6.     let right = numbers.slice(Math.floor(numbers.length / 2))
  7.     return merge(sort(left), sort(right))
  8. }
  9. let merge = (a, b) => {
  10.     if (a.length === 0) {
  11.         return b
  12.     }
  13.     if (b.length === 0) {
  14.         return a
  15.     }
  16.     return a[0] > b[0] ?
  17.         [b[0]].concat(merge(a, b.slice(1))) : [a[0]].concat(merge(a.slice(1), b))
  18. }

时间复杂度

O(nlogn)

优缺点

优点

稳定，最优和最恶劣的情况，时间复杂度都是，O(nlogn)，当数据足够庞大时，我们就喜欢稳定的复杂度。

缺点

缺点是辅存很大，适合对象排序