参考文章：
1. 冒泡排序
思路
- 比较所有相邻元素，如果第一个比第二个大，则交换它们
- 一轮下来，可以保证最后一个数是最大的
- 执行n-1轮，就可以完成排序
代码
Array.prototype.bubbleSort = function () {
for (let i = 0; i < this.length - 1; i++) {
let hasSwapped = false // 本轮是否有交换行为
for (let j = 0; j < this.length - 1 - i; j++) {
if (this[j] > this[j + 1]) {
hasSwapped = true
const temp = this[j]
this[j] = this[j + 1]
this[j + 1] = temp
}
}
// 若本轮没有交换行为，则无需再进行下一轮遍历
if (!hasSwapped) {
break;
}
}
}
const arr = [5, 4, 3, 2, 1]
arr.bubbleSort()
console.log('arr', arr)
分析
- 时间复杂度：
- 最好：O(n)【已排好序的数组，没有交换，一轮遍历完成】
- 最坏：O(n2)
- 平均：O(n2)
- 空间复杂度：O(1)
- 排序方式：In-place
- 稳定性：稳定
2. 选择排序
思路
- 找到数组中的最小值（用indexMin来表示当前值下标，遍历遇到更小的就替换为它），将其放置在第一位（和原第一位交换）
- 接着找到第二小的值，选中它并将其放置在第二位
- 以此类推，执行n-1轮
代码
Array.prototype.selectionSort = function () {
for (let i = 0; i < this.length - 1; i++) {
let indexMin = i
for (let j = i; j < this.length; j++) {
if (this[j] < this[indexMin]) {
indexMin = j
}
}
// 若当前位就是最小位，则不交换
if (indexMin !== i) {
const temp = this[i]
this[i] = this[indexMin]
this[indexMin] = temp
}
}
}
const arr = [5, 4, 3, 2, 1]
arr.selectionSort()
console.log('arr', arr)
分析
- 时间复杂度：
- 最好：O(n2)
- 最坏：O(n2)
- 平均：O(n2)
- 空间复杂度：O(1)
- 排序方式：In-place
- 稳定性：不稳定
3. 插入排序
思路
- 将一个元素插入到前面排序的子序列中，使插入后的子序列仍然是排序的，n个元素共需n-1趟
- 从第二个数开始往前比，比他大就往后排，以此类推进行到最后一个数
代码
Array.prototype.insertionSort = function () {
for (let i = 1; i < this.length; i++) {
const num = this[i];
for (let j = i - 1; j >= 0; j--) {
if (num < this[j]) {
this[j + 1] = this[j]
}
else {
break
}
}
this[j + 1] = num
}
}
const arr = [5, 4, 3, 2, 1]
arr.insertionSort()
console.log('arr', arr)
分析
- 时间复杂度：
- 最好：O(n)
- 最坏：O(n2)
- 平均：O(n2)
- 空间复杂度：O(1)
- 排序方式：In-place
- 稳定性：稳定
4. 归并排序
思路
- 分：把数组劈成两半，再递归地对子数组进行“分”操作，直到分成一个个单独的数
- 合：把两个数合并为有序数组，再对有序数组进行合并，直到全部子数组合并为一个完整数组
- 合并两个有序数组
- 新建一个空数组res，用于存放最终排序后的数组
- 比较两个有序数组的头部，较小者出队并推入res中
- 如果两个数组还有值，就重复第二步
- 合并两个有序数组
代码
Array.prototype.mergeSort = function () {
// 终点
if (this.length === 1) {
return this
}
// 分
const mid = Math.floor(this.length / 2)
const left = this.slice(0, mid)
const right = this.slice(mid)
left.mergeSort()
right.mergeSort()
// 合
let res = []
while (left.length > 0 || right.length > 0) {
if (left.length > 0 && right.length > 0) {
left[0] < right[0] ? res.push(left.shift()) : res.push(right.shift())
}
else if (left.length > 0) {
res.push(left.shift())
} else {
res.push(right.shift())
}
}
// res 拷贝到 this
res.forEach((item, i) => {
this[i] = item
})
}
const arr = [5, 4, 3, 2, 1]
arr.mergeSort()
console.log('arr', arr)
分析
- 时间复杂度：
- 最好：O(nlogn)
- 最坏：O(nlogn)
- 平均：O(nlogn)
- 轮数：O(logn)
- 每轮遍历：O(n)
- 空间复杂度：O(n)
- 临时的数组 n + 递归时压入栈的数据占用的空间 logn
- 排序方式：Out-place
- 稳定性：稳定
5. 快速排序
思路
- 分区：在数据序列中选择一个元素作为基准值，每趟从数据序列的两端开始交替进行，将小于基准值的元素交换到序列前端，将大于基准值的元素交换到序列后端，介于两者之间的位置则成为基准值的最终位置（将基准值与最终位置或其前一位元素交换）。
- 递归：递归地对基准前后的子数组进行分区
代码
Array.prototype.quickSort = function () {
// end: 包括
const rec = (start, end) => {
if (end <= start) {
return
}
const pivot = this[start]
let i = start + 1
let j = end
while (i < j) {
while (this[i] <= pivot && i < j) {
i++
}
while (this[j] >= pivot && i < j) {
j--
}
// 若i<j,i和j交换
if (i < j) {
let temp = this[i]
this[i] = this[j]
this[j] = temp
}
}
// i == j 的情况
if (this[i] < pivot) {
// i和pivot交换
let temp = this[i]
this[i] = this[start]
this[start] = temp
rec(start, i - 1)
rec(i + 1, end)
} else {
// i-1和pivot交换
let temp = this[i - 1]
this[i - 1] = this[start]
this[start] = temp
rec(start, i - 2)
rec(i, end)
}
}
rec(0, this.length - 1)
}
const arr = [3, 1, 5, 4, 2]
arr.quickSort()
console.log('arr', arr)
分析
- 时间复杂度：
- 最好：O(nlogn)
- 最坏：O(n2)【每轮选择的基准值都是极端值（最小/最大）】
- 平均：O(nlogn)
- 轮数：O(logn)
- 每轮遍历：O(n)
- 空间复杂度：O(logn)
- 递归时压入栈的数据占用的空间 logn
- 排序方式：In-place
- 稳定性：不稳定