13、用JS实现快速排序

固定算法，固定思路

• 找到中间位置midValue
• 遍历数组，小于midValue放在left，否则放在right
• 继续递归。最后concat拼接，返回

细节

• 获取midValue的两种方式：
• 使用splice，会修改原数组
• 使用slice，不会修改原数组——更加推荐

代码实现

• splice方式

function quickSort1 (arr:number[]):number[] {
  const len = arr.length
  if (len === 0) return arr
   
  const midIdx = Math.floor(len / 2)
  const midValue = arr.splice(midIdx,1)[0]

  const left:number[] = []
  const right:number[] = []

  // 由于splice改变了原数组，所以不能使用len作为循环条件
  for (let i = 0; i < arr.length; i++) {
    
    if (arr[i] < midValue) {
      // 小于中间值，放left
      left.push(arr[i])
    } else {
      // 大于或者等于，放right
      right.push(arr[i])
    }
    
  }

  return quickSort1(left).concat([midValue],quickSort1(right))
}
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

• slice方式

function quickSort2 (arr:number[]):number[] {
  const len = arr.length
  if (len === 0) return arr
   
  const midIdx = Math.floor(len / 2)
  const midValue = arr.slice(midIdx,midIdx + 1)[0]

  const left:number[] = []
  const right:number[] = []

  for (let i = 0; i < len; i++) {
    if (i !== midIdx) {
      if (arr[i] < midValue) {
        // 小于中间值，放left
        left.push(arr[i])
      } else {
        // 大于或者等于，放right
        right.push(arr[i])
      }
    }
    
    
  }

  return quickSort2(left).concat([midValue],quickSort2(right))
}
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

功能测试

• 测试splice方式

const arr1 = [1,6,2,4,3,7,5,8,9]

quickSort1(arr1)
1
2
3

结果

[1, 2, 3, 4, 5, 6, 7, 8, 9]
1

• 测试slice方式

const arr1 = [1,6,2,4,3,7,5,8,9]

quickSort2(arr1)
1
2
3

结果

[1, 2, 3, 4, 5, 6, 7, 8, 9]
1

单元测试

describe('快速排序', () => {
  it('正常情况', () => {
    const arr = [1, 6, 2, 4, 3, 7, 5, 8, 9]
    const res = quickSort1(arr)
    expect(res).toEqual([1, 2, 3, 4, 5, 6, 7, 8, 9])

    const arr2 = [1, 6, 2, 4, 3, 7, 5, 8, 9]
    const res2 = quickSort2(arr2)
    expect(res2).toEqual([1, 2, 3, 4, 5, 6, 7, 8, 9])
  })

  it('有负数', () => {
    const arr = [-1, -6, 2, 4, 3, 7, 5, 8, 9]
    const res = quickSort1(arr)
    expect(res).toEqual([-6, -1, 2, 3, 4, 5, 7, 8, 9])

    const arr2 = [-1, -6, 2, 4, 3, 7, 5, 8, 9]
    const res2 = quickSort2(arr2)
    expect(res2).toEqual([-6, -1, 2, 3, 4, 5, 7, 8, 9])
  })

  it('数值一样', () => {
    const arr = [2, 2, 2, 2]
    const res = quickSort1(arr)
    expect(res).toEqual([2, 2, 2, 2])

    const arr2 = [2, 2, 2, 2]
    const res2 = quickSort2(arr2)
    expect(res2).toEqual([2, 2, 2, 2])
  })

  it('空数组', () => {
    const res = quickSort1([])
    expect(res).toEqual([])

    const res2 = quickSort2([])
    expect(res2).toEqual([])
  })
})
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

性能测试

const test1 = []
for (let i = 0; i < 100 * 10000; i++) {
  const n = Math.floor(Math.random() * 10000)
  test1.push(n)
}
console.time('quickSort1')
quickSort1(test1)
console.timeEnd('quickSort1')

const test2 = []
for (let i = 0; i < 100 * 10000; i++) {
  const n = Math.floor(Math.random() * 10000)
  test2.push(n)
}

console.time('quickSort2')
quickSort2(test2)
console.timeEnd('quickSort2')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

打印结果

quickSort1: 713.186ms
quickSort2: 685.652ms
1
2

复杂度分析

• 有遍历，有二分——O(n*logn) 或者O(nlogn)
• (常规排序，嵌套循环，复杂度是O(n^2))

splice 和 slice 没有区分出来

• 算法本身的时间复杂度就够高O(n*logn)
• 外加，splice是逐步 二分 之后执行的，二分会快速削减数量级
• 如果单独比较splice和slice，效果会非常明显

const test1 = []
for (let i = 0; i < 100 * 10000; i++) {
  const n = Math.floor(Math.random() * 10000)
  test1.push(n)
}

console.time('splice')
test1.splice(50 * 10000 , 1)
console.timeEnd('splice')

const test2 = []
for (let i = 0; i < 100 * 10000; i++) {
  const n = Math.floor(Math.random() * 10000)
  test2.push(n)
}

console.time('slice')
test1.slice(50 * 10000 ,50 * 10000 + 1)
console.timeEnd('slice')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

打印结果

splice: 0.657ms
slice: 0.021ms
1
2

slice 本身优于splice

总结

• 常见排序算法
• 有二分，时间复杂度就包含O(logn)
• 注意数组操作：splice 和 slice的区别