【数据结构与算法】(15):快速排序


字数:565 阅读时长:3分钟 阅读:85

经典算法:给一个乱序的 number[] 数组,使用快速排序算法进行排序。

数据结构与算法 · 快速排序

一、固定算法,固定思路

  1. 找到中间位置 midValue
  2. 遍历数组,小于 midValue 放在 left,否则放在 right
  3. 继续递归。最后 concat 拼接,返回新数组

二、代码演示

  1. 快速排序 (使用 splice)
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
type IArrNumber = number[]

// 快速排序 (使用 splice)
export function quickSort1(arr:IArrNumber): IArrNumber {
const len = arr.length;
if (len <= 1) return arr;

const midIndex = Math.floor(len / 2)
const midValue = arr.splice(midIndex, 1)[0]

const left: IArrNumber = []
const right: IArrNumber = []

for (let i = 0; i < arr.length; i++) {
const n = arr[i]

if (n < midValue) {
// 小于 midValue , 则放在 left
left.push(n)
} else {
// 大于 midValue , 则放在 right
right.push(n)
}
}

return quickSort1(left).concat(
[midValue],
quickSort1(right)
)
}
  1. 快速排序 (使用 slice)
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
export function quickSort2(arr:IArrNumber): IArrNumber {
const len = arr.length;
if (len <= 1) return arr;

const midIndex = Math.floor(len / 2)
const midValue = arr.slice(midIndex, midIndex + 1)[0]

const left: IArrNumber = []
const right: IArrNumber = []

for (let i = 0; i < len; i++) {
if (i !== midIndex) {
const n = arr[i]

if (n < midValue) {
// 小于 midValue , 则放在 left
left.push(n)
} else {
// 大于 midValue , 则放在 right
right.push(n)
}
}
}

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import { quickSort1, quickSort2 } from './../quick-sort.ts'

describe('快速排序 splice', () => {
it('正常情况', () => {
const arr = [1, 8, 3, 9, 4, 35, 5, 6, 7,]
let res = quickSort1(arr)
expect(res).toEqual([1, 3, 4, 5, 6, 7, 8, 9, 35])
})
it('有负数', () => {
let arr = [-1,1,-2,7]
let res = quickSort1(arr)
expect(res).toEqual([-2,-1,1,7])
})
it('数组元素都一样', () => {
let arr = [2,2,2,2]
let res = quickSort1(arr)
expect(res).toEqual([2,2,2,2])
})
it('空数组', () => {
let res = quickSort1([])
expect(res).toEqual([])
})
})


describe('快速排序 slice', () => {
it('正常情况', () => {
const arr = [1, 8, 3, 9, 4, 35, 5, 6, 7,]
let res = quickSort2(arr)
expect(res).toEqual([1, 3, 4, 5, 6, 7, 8, 9, 35])
})
it('有负数', () => {
let arr = [-1,1,-2,7]
let res = quickSort2(arr)
expect(res).toEqual([-2,-1,1,7])
})
it('数组元素都一样', () => {
let arr = [2,2,2,2]
let res = quickSort2(arr)
expect(res).toEqual([2,2,2,2])
})
it('空数组', () => {
let res = quickSort2([])
expect(res).toEqual([])
})
})

四、算法复杂度

方法时间复杂度
for + spliceO(n*logn)
for + sliceO(n*logn)

欢迎访问:天问博客

本文作者: Tiven
发布时间: 2023-07-23
最后更新: 2023-07-24
本文标题: 【数据结构与算法】(15):快速排序
本文链接: https://www.tiven.cn/p/69e45d4b/
版权声明: 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处!
欢迎留言,提问 ^_^
个人邮箱: tw.email@qq.com
notification icon
博客有更新,将会发送通知给您!