1 选择排序
-
公式
image.png 代码
const selectSort = arr => {
if (arr.length <= 1) return arr
for (let i = 0; i < arr.length - 1; i++) { // 一共选择 length - 1 次，因为最后一次只有一个元素不用选
let minIndex = i // 假设第一个是最小的
for(let k = i + 1; k < arr.length; k++){
if(arr[k] < arr[i]){
minIndex = k // 第 k 个比第一个小，就用 minIndex 记住 k
}
}
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]] // 交换 arr[i] 和 arr[minIndex] 的值
}
return arr
}
selectSort([3, 2, 1]) // [1, 2, 3]
selectSort([1, 2, 1]) // [1, 2, 3]
- 时间复杂度
n + (n - 1) + (n - 2) + ... + 1
约等于n + n + n + ... + n
即 O(n^2)
思维特点
分而治之
把一个问题分解为两个相对简单的问题降低规模
每次规模减少1
2 计数排序
-
思路
image.png 代码
const countSort = arr => {
if(arr.length <= 1) return arr
let hashTable = {} // 用于计数的对象
let max = arr[0] // 用于记录最大值，假设第一个最大
for(let i = 0; i < arr.length; i++){
const n = arr[i]
hashTable[n] = hashTable[n] === undefined ? 1 : hashTable[n] + 1 // n 对应的 value 要么置为1，要么加1
if(n > max) max = n // 更新最大值
}
const result = [] // 要返回的数组
console.log('hashTable')
console.log(hashTable)
for(let k = 1; k <= max; k++){ // 正整数数组从1开始
if(hashTable[k] !== undefined){ // hashTable[k] 表示数字出现的次数
for(let m = 0; m < hashTable[k]; m++){
result.push(k) // 出现几次，就 push 几次
}
}
}
return result
}
countSort([3,2,1])
// [1, 2, 3]
countSort([1,2,1])
// [1, 1, 2]
思维特点
- 空间换时间
用一个 hash table 计数，两次遍历解决问题
第一次遍历将数组遍历到 hash table
第二次遍历 i 从 1 到 max ( max 为最大值)
时间复杂度降为O(n + max)
- 在某些情况下效率很低
元素个数比较少，值跨度大时
比如[1, 99999, 5555] 排序时就很慢
3 冒泡排序
- 思路(辅助技巧)
每次通过相邻元素两两对比来获取最大/小值
先画图找规律，再写代码
image.png
- 代码
const bubbleSort = arr => {
const {length} = arr
for(let r = 0; r < arr.length -1; r++){
for(let i = 0; i < arr.length - r - 1; i++){
if(arr[i] > arr[i + 1]){
[arr[i], arr[i + 1]] = [arr[i + 1], arr[i]]
}
}
}
return arr
}
bubbleSort([3,2,1])
// [1, 2, 3]
bubbleSort([1,2,1])
// [1, 1, 2]
- 思路
类似于选择排序
但是是通过相邻两两对比来选出最大或最小的一个
而选择排序是将每个元素与第一个元素对比
- 特点
时间复杂度 n + (n - 1) + (n - 2) + ... + 1 约等于 n ^2
是一个低效的算法，不过面试可能会问到
4 插入排序
image.png
每次起牌，将新牌插入到第一个比它小的牌的后面
虽然叫做插入排序，但是最好不要用 splice 方法，因为 splice 会导致整体移动
-
起牌、插牌
image.png -
细节
image.png 代码
const insertSort = arr => {
if(arr.length<=1)return arr
for(let s=1; s<arr.length; s++){
const n = arr[s] // 记住n
let i // i要在for循环之后使用
for(i=s-1; i>=0; i--){
//比 n 大的数字往后挪了一位
if(arr[i]>n) arr[i+1] = arr[i]
// 遇到比 n 小的就中断循环
else if(arr[i]<=n) break
}
arr[i+1] = n
}
return arr
}
insertSort([3,2,1])
// [1, 2, 3]
insertSort([1,2,1])
// [1, 1, 2]
插入排序复杂度
- O(n^2)
最差情况 1 + 2 + 3 + ... + n - 1 + n
- 如何优化
插入的时候不要从右往左一个一个对比
而是使用二分查找法，这样可以快速找到正确的位置
但插入的时候会引起整体挪动，所以复杂度并没有降低
5 二分查找法
- 需求
一个已经排好的数组 arr
一个数字 n
请告诉我 arr 里有没有跟 n 一样大的数字
- 思路
将 arr 中间的元素与 n 对比，如果相等就找到了
如果比 n 大，就用 arr[0..mid]进行第一步
如果比 n 小，就用 arr[mid..len]进行第一步
直到数组长度缩为0，还找不到就是找不到了
- 代码(递归写法)
bSearch = (arr, n, start, end)=>{
if(end === start) return -1
let mid = parseInt((start + end) / 2) //某些语言会溢出
console.log(mid)
return n === arr[mid] ? mid :
n > arr[mid] ? bSearch(arr,n,mid+1,end) :
n < arr[mid] ? bSearch(arr,n,start,mid) :
undefined
}
bSearch([2,2,2,4,5,6,7],1,0,7)
/*log: 3
* log: 1
* log: 0
* 结果：-1
* 7个数字只需要查找3次
* */
排序算法总结
image.png
时间复杂度总结
image.png
参考文章：十大经典排序算法
