排序
狐七 3/22/2022 算法
# 原理
# 1. 冒泡排序如何实现，时间复杂度是多少？
查看答案
冒泡算法的原理：
- 升序冒泡：两次循环，相邻元素两两比较，如果前面的大于后面的就交换位置
- 降序冒泡：两次循环，相邻元素两两比较，如果前面的小于后面的就交换位置
冒泡排序的性能：
- 冒泡排序在平均和最坏情况下的时间复杂度都是 O(n^2)
- 空间复杂度是 O(1)
- 稳定
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - 1 - i; j++) {
if(arr[j] > arr[j+1]) {
let temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
}
}
}
}
bubbleSort(arr)
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 2. 插入排序
查看答案
- 插入排序原理是分成有序区和无序区，将无序区中的元素插入到有序区当中，直到全部都成为有序区。
- 最开始的时候单个元素看做是有序的。
- 时间复杂度 O(n^2
- 空间复杂度 O(1)
- 稳定
function sort (arr) {
for(let i = 1; i < arr.length; i++) {
let temp = arr[i]
for (let j = i - 1; j >= 0; j--) {
if(arr[j] > temp) {
arr[j+1] = arr[j]
if(j === 0) arr[j] = temp
} else {
arr[j+1] = temp
break;
}
}
}
}
sort(arr)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 3. 归并排序
查看答案
- 简单理解，如果是两个有序数组排序如何排？每个数组头部进行比较，小的弹出，直到遍历完成。
- 如果将每个数组元素都理解成一个有序数组，进行归并，直到归并成一个完整的数组。
- 时间复杂度 O(n * logn)
- 空间复杂度 O(n)
- 稳定
function mergeSort(arr) {
if (arr.length < 2) return arr
let mid = arr.length >> 1
// 将数组分解成两边
let left = arr.slice(0,mid)
left = mergeSort(left)
let right = arr.slice(mid, arr.length)
right = mergeSort(right)
// 合并数组
return merge(left, right)
}
function merge (l, r) {
let len = l.length + r.length
let res = []
let lindex = 0
let rindex = 0
// 遍历，把小的放进数组里
for (let i = 0; i < len; i++) {
if(lindex < l.length && rindex < r.length) {
if (l[lindex] <= r[rindex]) {
res.push(l[lindex++])
} else {
res.push(r[rindex++])
}
} else if (lindex >= l.length) {
res.push(r[rindex++])
} else {
res.push(l[lindex++])
}
}
return res
}
const arr1 = mergeSort(arr)
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
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
# 4. 快速排序
查看答案
- 找到一个数作为参考，比这个数字大的放在数字左边，比它小的放在右边； 然后分别再对左边和右变的序列做相同的操作
- 时间复杂度 O(n * logn)
- 不稳定
function quickSort (arr) {
if (arr.length <= 1) return arr
const left = []
const right = []
const current = arr.splice(0, 1)[0] // 注意splice之后，长度少了一个
for(let i = 0; i < arr.length; i++) {
if(arr[i] < current) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return quickSort(left).concat(current, quickSort(right)) // 递归
}
quickSort(arr)1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 变形题
# 1. 有一个数组，里面是人名和分数，按照分数进行排序
const arr = [{name: 'xm', score: 97}, {name: 'xh', score: 92}, {name: 'xl', score: 95}, {name: 'xq', score: 96}]
查看答案
arr.sort((a, b) => b.score - a.score)