冒泡排序
思路：判断相邻元素的大小，交换位置，每次循环会得到在该次循环中最大的数，像气泡一样升到顶端，称为冒泡
//冒泡
function fn1(arr) {
for (let i = 0; i < arr.length - 1; i++) {
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
let a = arr[j + 1]
arr[j + 1] = arr[j]
arr[j] = a
}
}
}
return arr
}
快速排序
思路：有些分治思想，从数组中随便取一个数为比较基准（我一般是取第一个），基准数左侧都比基准小，右侧都比基准大，然后再在左右两个区域重复上述步骤，直到所有元素都变得有序
递归法
//快排 递归版
function fn2_recursion(arr) {
let leftArr = []
let rightArr = []
let baseEl
if (arr.length == 1 || arr.length == 0) {
return arr
}
for (let i in arr) {
if (i == 0) {
baseEl = arr[0]
continue
}
if (arr[i] >= baseEl) {
rightArr.push(arr[i])
} else {
leftArr.push(arr[i])
}
}
return [...fn2(leftArr), baseEl, ...fn2(rightArr)]
}
递归法在没有递归思维的情况下，感觉很绕，熟练之后很简单，但是容易造成栈溢出
迭代版
//快排 迭代
function fn2(arr) {
let assistStack = [arr]
while (assistStack.length < arr.length) {
let baseEl
let leftArr = []
let rightArr = []
for (let i of assistStack) {
if (i.length !== 1) {
for (let j in i) {
if (j == 0) {
baseEl = [i[0]]
continue
}
if (i[j] >= baseEl) {
rightArr.push(i[j])
} else {
leftArr.push(i[j])
}
}
let index = assistStack.indexOf(i)
if (leftArr.length !== 0) {
assistStack.splice(index, 1, leftArr, baseEl)
index += 2
} else {
assistStack.splice(index, 1, baseEl)
index += 1
}
if (rightArr.length !== 0) {
assistStack.splice(index, 0, rightArr)
}
//console.log(assistStack)
break
}
}
}
//将结果合并
for (let i in assistStack) {
assistStack[i] = assistStack[i][0]
}
return assistStack
}
迭代通常来说复杂的多，主要是状态的保存，万物皆有套路
插入排序
思路：将原数组分成左右两个区域，从右边拿出元素，与左边的区域比较，然后插入到正确的位置，左边区域从零开始扩张，右侧逐渐减小到零
//插排
function fn3(arr) {
let res = []
for (let i in arr) {
if (i == 0) {
res.push(arr[i])
continue
}
for (let j = 0; j < res.length; j++) {
if (j == res.length - 1) {
res.push(arr[i])
break
}
if (arr[i] <= res[j]) {
res.splice(j, 0, arr[i])
break
}
if (arr[i] > res[j] && arr[i] <= res[j + 1]) {
res.splice(j + 1, 0, arr[i])
break
}
}
}
return res
}
选择排序
思路：分成左右两个区域，遍历右侧区域，找到最小的push到左侧区域，和插入排序感觉好像，体感不同的是，插入排序对每个元素依次排序，选择排序不一定排哪个
//选择排序
function fn4(arr) {
let res = []
let copyArr = arr.slice()
for (let j = 0; j < arr.length; j++) {
let min = Number(Infinity)
let delIndex = -1
for (let i in copyArr) {
if (copyArr[i] < min) {
min = copyArr[i]
delIndex = i
}
}
if(delIndex == -1){
break
}
res.push(copyArr[delIndex])
copyArr.splice(delIndex, 1)
}
return res
}
归并排序
思路：分治思想，先分再治，字越少越抽象是真理
// 归并排序 递归
function fn5_recursion(arr){
let [l,r] = slice(arr)
if(l.length > 1 || r.length > 1){
return merge(fn5_recursion(l),fn5_recursion(r))
}
let res = merge(l,r)
//console.log(res)
return res
function slice(arr){
let sliceIndex = Math.floor(arr.length/2)
let leftArr = arr.slice(0,sliceIndex)
let rightArr = arr.slice(sliceIndex)
//console.log(leftArr,rightArr)
return [leftArr,rightArr]
}
function merge(leftArr,rightArr){
let i = 0;
let j = 0;
let res = []
while(i < leftArr.length || j < rightArr.length){
//console.log(res,'hahah',leftArr,rightArr)
if(i == leftArr.length){
res.push(rightArr[j])
j++
continue
}
if(j == rightArr.length){
res.push(leftArr[i])
i++
continue
}
if(leftArr[i] < rightArr[j]){
res.push(leftArr[i])
i++
} else {
res.push(rightArr[j])
j++
}
}
//console.log(leftArr,rightArr,res)
return res
}
}
今天先搞五种，明天续杯 奥利给
