面试官：你的排序算法还能优化吗？？
站长
· 阅读数 14
面试中有些手撕会考一些排序算法，如果没理解原理可能现场一个冒泡排序都要调试5，6分钟🤓那印象就不太好了。接下来带大家用最易理解的且代码量最短的讲清楚排序！ 承接上文，十大排序算法还有7个算法没实现，分别是冒泡，选择，插入，希尔，桶排序，基数排序，计数排序。话不多说，coding！
实现
接下来的排序就稍微简单些，但有些临界条件考虑不周到也容易写错，那么仍然承接以最短的代码实现逻辑清晰的排序
冒泡排序
- 算法描述
- 通过扫描每一趟元素，按照升序或者降序的逻辑，使最大或最小的元素加入到有序序列中
- i 表示需要冒泡多少趟 其实只需要
length - 1趟就ok 因为最后一趟一个元素也冒泡不了 - j表示无序数组的首尾 每一趟
i可以增加一个有序元素，同时无序数组的尾 - 1，体现在length - i - 1 - 如果这个元素比下个元素大的话就交换(也就是冒泡的由来) 直至无序序列的尾
- gif图解
十行冒泡
const bubbleSort = (array, length = array.length) => {
for (let i = 0; i < length - 1; i++) {
for (let j = 0; j < length - i - 1; j++) {
if (array[j] > array[j + 1]) {
;[array[j], array[j + 1]] = [array[j + 1], array[j]]
}
}
}
return array
}
选择排序
- 算法描述
- 按照一定逻辑，如果升序那么就是从后往前遍历，每一趟从无序序列的尾部到首部搜索比较max，记录最大的元素，最后和尾元素交换。反之，如果是降序那么就是前往后遍历，找到最小的元素最后和首元素交换。
- 其中i表示需要当前待有序化的元素指针，j表示无序序列从尾部到首部的指针，每一趟i都会向前走一步即
i--，j的尾部始终是从i开始遍历直至0下标 - 用max标记每一趟最大的元素，最后和当前元素交换，以此逐渐序列化
- gif图解
十行选择排序
const selectSort = (array, length = array.length) => {
for (let i = length - 1; i > 0; i--) {
let max = i
for (let j = i; j >= 0; j--) {
max = array[max] > array[j] ? max : j
}
;[array[i], array[max]] = [array[max], array[i]]
}
return array
}
插入排序（希尔排序）
-
算法描述
- 其实插入排序和希尔排序类似，核心思想就是将元素插入到有序序列中，而希尔排序在更大数据中表现更优秀
- 总体来说，插入排序是将无序元素插入到有序序列中，其过程类似于打牌，无序元素需要通过和有序序列中的每个元素一一比较->覆盖->最后交换，最后完成序列化。希尔排序通过比较相距一定间隔gap的元素来进行，各趟比较所用的距离随着算法的进行而减小
Math.floor(gap / 2)，每一趟都会更加有序，直到只比较相邻元素的最后一趟排序为止完成序列化 - i表示无序元素指针，每一趟无序序列都会 - 1 即i++。j表示i之前的priot所有有序序列元素，如果j的下标仍有效即
>= 0并且按照一定逻辑比对应无序序列的值priot比较，如果满足，则j + 1覆盖 j下标对应的值，并且有序序列对应的指针向前j--直到找到适合无序元素i适合的位置再和有序元素j + 1交换值
-
gif图解
十二行插入排序
const insertSort = (array, length = array.length) => {
for (let i = 1; i < length; i++) {
let j = i - 1
const priot = array[i]
while (j >= 0 && array[j] > priot) {
array[j + 1] = array[j]
j--
}
array[j + 1] = priot
}
return array
}
希尔排序
- 算法描述
- 和插入排序类似，但是增加了
gap(比较间距)，使得排序算法更加高效，有序化速度更快 - 每一趟都可让间距为gap之间的元素有序化
- 可以发现其实如果插入排序能写出来，直接将插入排序的间距
1换成gap，就可以accept
- 和插入排序类似，但是增加了
- 图解
十四行希尔排序
const shellSort = (array, length = array.length)=> {
for (let gap = Math.floor(length / 2); gap > 0; gap = Math.floor(gap / 2)) {
for (let i = gap; i < length; i++) {
let j = i - gap
const priot = array[i]
while (j >= 0 && array[j] > priot) {
array[j + gap] = array[j]
j -= gap
}
array[j + gap] = priot
}
}
return array
}
桶排序
- 算法描述
- 桶排序是一种非比较排序算法，适用于在已知数据范围的情况下对一组数据进行排序
- 首先确定数据范围，找出最大值（max）和最小值（min）再根据数据范围和数据量创建若干个桶
- 将数据根据大小分配到对应的桶中，可以使用以下公式确定桶的索引：index = Math.floor(((num - min) / (max - min + 1)) * bucketCount)对每个非空的桶内数据进行排序
- 最后，按照桶的顺序将数据合并起来
flat或者concat，即可得到有序化序列
- gif图解
十一行极简代码
const bucketSort = (array, length = array.length) {
const max = Math.max(...array)
const min = Math.min(...array)
const bucketCount = Math.floor((max - min) / length) + 1
const buckets = Array.from({ length: bucketCount }, () => [])
for (let num of array) {
const index = Math.floor(((num - min) / length) * (bucketCount - 1))
buckets[index].push(num)
}
return buckets.map(bucket => bucket.sort((a, b) => a - b)).flat()
}
基数排序和基数排序比较易懂，看过之前的代码看这个代码应该不是问题，我就直接贴图解和代码咯
十三行计数排序
const countSort = array => {
const min = Math.min(...array)
const max = Math.max(...array)
const countArray = new Array(max - min + 1).fill(0)
for (let num of array) countArray[num - min]++
for (let i = min, sortIndex = 0; i <= max; i++) {
while (countArray[i - min] > 0) {
array[sortIndex++] = i
countArray[i - min]--
}
}
return array
}
十二行基数排序
- gif 图解
const radixSort = array => {
const digitLength = Math.max(...array).toString().length
for (let i = 0; i < digitLength; i++) {
const bucket = Array.from({ length: 10 }, () => [])
for (let num of array) {
const digit = Math.floor(num / 10 ** i) % 10
bucket[digit].push(num)
}
array = bucket.flat()
}
return array
}
测试代码取自我上一篇文章
看看你们的排序实力！
我们虽然只有一个nlogn的希尔排序，但是我认为我的冒泡可以差到哪里去！实践一下！coding!
写一个测试时间的函数
genRandomList生成10000个随机数的数组testCostTime计算消耗的时间isOrder并且判断是否是有序的result.slice切片前20个数看看效果
// testTime.js
const genRandomList = () => {
const array = Array.from({ length: 10000 }, (_, index) => index)
for (let i = 0; i < array.length; i++) {
let randomIndex = Math.floor(Math.random() * (i + 1))
;[array[randomIndex], array[i]] = [array[i], array[randomIndex]]
}
return array
}
const testCostTime = (array, sort, name) => {
const start = performance.now()
let result = sort(array)
let isOrder = result?.every((value, index, array) => index == 0 || value >= array[index])
console.log(`${name} 耗时 ${performance.now() - start} ${isOrder ? '排序正确' : '排序错误'} ${result?.slice(0, 20)}`)
}
export { genRandomList, testCostTime }
Promise.all实现异步同时测试
- 用
genRandomList统一生成的array增加公平性 testAlgorithmTime封装一层Promise来异步调用- 用
Promise.all包裹测试的promise
//index.js
import bucketSort from './bucket.js'
import countSort from './count.js'
import radixSort from './radix.js'
import { shellSort, insertSort } from './shell.js'
import selectSort from './select.js'
import bubbleSort from './bubble.js'
import { testCostTime, genRandomList } from './testTime.js'
const array = genRandomList()
const testAlgorithmTime = (array, algorithm, name) => {
return new Promise(resolve => {
testCostTime(array, algorithm, name)
resolve()
})
}
Promise.all([
testAlgorithmTime(array, countSort, 'countSort'),
testAlgorithmTime(array, bucketSort, 'bucketSort'),
testAlgorithmTime(array, radixSort, 'radixSort'),
testAlgorithmTime(array, selectSort, 'selectSort'),
testAlgorithmTime(array, bubbleSort, 'bubbleSort'),
testAlgorithmTime(array, insertSort, 'insertSort'),
testAlgorithmTime(array, shellSort, 'shellSort'),
])
.then(e => {
console.log('测试完成')
})
.catch(error => {
console.error('出现错误：', error)
})
测试结果 🎉🎉🎉
居然shellSort和insertSort和countSort相差不大！但也算符合预期 收工！ ✨