在写排序之前我们需要先搞懂两个概念 排序的稳定性 和 时间复杂度
排序分为稳定排序和不稳定排序，稳定排序在排序过程中不会影响到想等数据之间的相对位置，如
1
2
3
// 我们为了方便标示 将2做区分为a2 和 b2
// const a = [2, 3, 2, 1]
const a = [a2, 3, b2, 1]冒泡排序的步骤是这样的
整个过程a2和b2的位置相对没有发生变化，因此冒泡排序属于稳定排序
选择排序是这样的
选择排序在排序过程中a2和b2的相对位置已经发生变化，因此选择排序属于不稳定排序
这个就直接看这篇文章：(数据结构)十分钟搞定算法的时间复杂度
1
2
// 数组为arr，将arr升序排列
const arr = [1, 3, 0, 88, 33, 22, 120, 4, 2, 2, 3, 52]冒泡排序是最常见的排序方式
1
2
3
4
5
6
7
8
9
10
const arr = [1, 3, 0, 88, 33, 22, 120, 4, 2, 2, 3, 52]
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
}
}
}
console.log(arr) // [0, 1, 2, 2, 3, 3, 4, 22, 33, 52, 88, 120]实现方式：
时间复杂度： O(n²) 两次for循环
1
2
3
4
5
6
7
8
9
10
const arr = [1, 3, 0, 88, 33, 22, 120, 4, 2, 2, 3, 52]
for (let i = 0; i < arr.length - 1; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j]) {
[arr[i], arr[j]] = [arr[j], arr[i]]
}
}
}
console.log(arr) // [0, 1, 2, 2, 3, 3, 4, 22, 33, 52, 88, 120]实现方式：
时间复杂度： O(n²) 两次for循环
1
2
3
4
5
6
7
8
9
10
const arr = [1, 3, 0, 88, 33, 22, 120, 4, 2, 2, 3, 52]
for (let i = 1; i < arr.length; i++) {
for (let j = i; j > 0; j --) {
if (arr[j] < arr[j - 1]) {
[arr[j - 1], arr[j]] = [arr[j], arr[j - 1]]
}
}
}
console.log(arr)实现方式
时间复杂度： O(n²) 两次for循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const arr = [1, 3, 0, 88, 33, 22, 120, 4, 2, 2, 3, 52]
function sort (lists) {
if (lists.length <= 1) {
return lists
}
const tmp = lists.splice(0, 1)[0]
let left = []
let right = []
lists.forEach((item) => {
if (tmp > item) {
left.push(item)
} else {
right.push(item)
}
})
return sort(left).concat(tmp, sort(right))
}
console.log(sort(arr))实现方式
左 - tmp - 右 连接完成快速排序操作
时间复杂度： O (nlogn)未完 待续
✏️ 如有问题，欢迎指正