冒泡排序
比较所有相邻的两项，如果第一个比第二个大，则交换他们
最好O(n) 最坏O(n^2) 平均O(n^2) 稳定
function bubbleSort(array) {
const length = array.length
// 外层循环控制比较的轮数
for (let i = 0; i < length; i++) {
// 里层循环控制每一轮比较的次数
// 使用 length - 1 - i 是为了减去外层循环已经排序过的趟数，优化次数
for (let j = 0; j < length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
let temp = array[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
return array
}
let arr = [1, 5, 3, 2, 4]
console.log(bubbleSort(arr))
// [1, 2, 3, 4, 5]
插入排序
假设第一项已经排序了，接着和第二项进行比较，取出第二项的索引和值，判断第二项应该待在原位还是插到第一项之前？这样，头两项就已经正确排序，接着已经排序好的再和第三项比较（它应该插入到第一、第二、还是原位置？），以此类推
最好O(n) 最坏O(n^2) 平均O(n^2) 稳定
function insertionSort(arr) {
const length = arr.length
// 假设索引0已经排序，所以从索引1开始遍历
for (let i = 1; i < length; i++) {
let j = i
let temp = arr[i]
// 循环遍历前一项
while (arr[j - 1] > temp && j > 0) {
// 将前一项后移
arr[j] = arr[j - 1]
j--
}
// 次数 j 既为需要插入的索引
arr[j] = temp
}
return arr
}
let arr = [1, 5, 3, 2, 4]
console.log(insertionSort(arr))
// [1, 2, 3, 4, 5]
模拟换牌
function insertionSort(arr) {
// 1.准备一个新数组，用来存储抓到手里的牌，开始先抓一张牌进来
let handle = []
handle.push(arr[0])
// 2.从第二项开始依次抓牌，一直把台面上的牌抓光
for (let i = 1; i < arr.length; i++) {
// A 是新抓的牌
let A = arr[i]
// 和 HANDLE 手里的牌依次比较（从后向前比）
for (let j = handle.length - 1; j >= 0; j--) {
// 没一次要比较的手里的牌
let B = handle[j]
// 如果当前的新牌 A 比要比较的牌 B 大，就把 A 放到 B 的后面
if (A > B) {
handle.splice(j + 1, 0, A)
break
}
// 已经比到第一项，我们把新牌放到手中最前面即可
if (j === 0) {
handle.unshift(A)
}
}
}
return handle
}
let arr = [1, 5, 3, 2, 4]
console.log(insertionSort(arr))
// [1, 2, 3, 4, 5]
快速排序
分而治之思想
-
选择基准值，一般是将开头、中间、末尾三个数先进行排序，中间值作为基准值
-
将数组分为左右两个子数组：小于基准值得元素组成的子数组和大于基准值得元素组成的子数组
-
对这两个子数组进行快速排序（递归）
最好O(nlog^n) 最坏O(n^2) 平均O(nlog^n) 不稳定
function quickSort(arr) {
// 4.结束递归，（当 arr 中小于等于一项，则不用处理）
if (arr.length <= 1) {
return arr
}
// 1.找到数组的中间值，在原有的数组中把它移除
let minddleIndex = Math.floor(arr.length / 2)
let minddleValue = arr.splice(minddleIndex, 1)[0]
// 2.准备左右两个数组，循环剩下数组中的每一项，
// 比当前项小的放到左边数组中，反之放到右边数组中
let arrLeft = []
let arrRight = []
for (let i = 0; i < arr.length; i++) {
let current = arr[i]
current < minddleValue ? arrLeft.push(current) : arrRight.push(current)
}
// 3.递归方式让左右两边的数组持续这样处理，一直到左右两边都排好序为止
// 最后让左边+中间+右边拼接为最后的结果
return quickSort(arrLeft).concat(minddleValue, quickSort(arrRight))
}
let arr = [1, 5, 3, 2, 4]
console.log(quickSort(arr))
// [1, 2, 3, 4, 5]