1、冒泡排序，时间复杂度O(n2)，
// 冒泡排序
function bubbleSort (arr) {
const len = arr.length
for (let i = 0; i < len; i++) { // 共需要排序的位数
for (let j = 0; j < len - i - 1; j++) { // 每次遍历确定最后一位
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
}
}
}
return arr
}
2、快速排序，时间复杂度O(nlogn)，是冒泡排序的优化版，将数组切割成左右两块，然后递归调用方法
// 快速排序
function quikSort (arr) {
const len = arr.length
if (len <= 1) return arr;
const midIdx = parseInt(len / 2)
const midVal = arr.splice(midIdx, 1)[0]
const left = [], right = [];
for (let val of arr) {
val < midVal ? left.push(val) : right.push(val)
}
return [...quikSort(left), midVal, ...quikSort(right)]
}
3、归并排序，
时间复杂度O(nlogn)，思想：将排序数组无限分割为左右两个数组，直到长度为1，然后开始合并相邻两个数组并排序
// 归并排序
function mergeSort (arr) {
const len = arr.length
if (len <= 1) return arr;
const midIdx = parseInt(len / 2)
const left = mergeSort(arr.slice(0, midIdx))
const right = mergeSort(arr.slice(midIdx))
return merge(left, right)
}
function merge (left, right) {
const lLen = left.length
const rLen = right.length
let l = 0, r = 0, res = [];
while (l < lLen && r < rLen) {
res.push(left[l] < right[r] ? left[l++] : right[r++])
}
return [...res, ...(l === lLen ? right.slice(r) : left.slice(l))]
}
4、选择排序，时间复杂度O(n2)，选出最小值，放在排好序的后面一位
// 选择排序
function selectSort (arr) {
for (let i = 0, len = arr.length; i < len; i++) {
let k = i
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[k]) k = j
}
[arr[k], arr[i]] = [arr[i], arr[k]]
}
return arr
}
5、插入排序，
时间复杂度O(n2)，遍历值与前面排好序的值进行比较，交换，最佳情况O(n)
// 插入排序
function insertSort (arr) {
for (let i = 1, len = arr.length; i < len; i++) {
let j = i
const val = arr[j]
while (j > 0 && val < arr[j - 1]) {
[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]
j--
}
}
return arr
}