做前端一直没怎么接触算法之类，看到一篇文章 - 十大经典排序算法总结（JavaScript描述）
学习过程中动手敲一敲其中的示例，接下来记录一下用 js 实现经典排序算法的过程。
冒泡排序（Bubble Sort）
冒泡排序，我的理解就是循环判断当前的数字和下一个数字的大小，如果当前大于下一个，则把当前的放到后面。这样子，排序完成后最后一个就是最大的数字。就像是气泡从水底冒上来一样。
const array = [10, 2, 23, 123, 12, 32, 34, 56, 1, 98, 11, 22, 33, 298, 4]
function sort (array) {
let result = [...[], ...array]
let count = 0
for (let i = 0; i < result.length; i++) {
for (let j = 0; j < result.length; j++) {
if (result[j] > result[j + 1]) {
const currentNumber = result[j]
const nextNumber = result[j + 1]
result[j] = nextNumber
result[j + 1] = currentNumber
}
count++
}
}
console.log('count', count) // 225
console.log(result) // [ 1, 2, 4, 10, 11, 12, 22, 23, 32, 33, 34, 56, 98, 123, 298 ]
}
sort(array)
冒泡排序最坏情况的时间复杂度是 （n²）。那么，优化一下。试想一下，冒泡排序时是从第一个开始，到最后一个。那经历一次循环后，最后一个肯定是最大的数。下一次排序则没必要比较最后一个，以此类推。接下来，改进的过程中，记录下最后一次比较的位置，下一次比较这个位置后面的就不去比较了。
const array = [10, 2, 23, 123, 12, 32, 34, 56, 1, 98, 11, 22, 33, 298, 4]
function sort (array) {
let result = [...[], ...array]
let lastExchangePosition = result.length
let exchangePosition = 0
let count = 0
for (let i = 0; i < result.length; i++) {
for (let j = 0; j < lastExchangePosition; j++) {
if (result[j] > result[j + 1]) {
const currentNumber = result[j]
const nextNumber = result[j + 1]
result[j] = nextNumber
result[j + 1] = currentNumber
exchangePosition = j
}
count++
}
lastExchangePosition = exchangePosition
}
console.log('count', count) // 109
console.log(result) // [ 1, 2, 4, 10, 11, 12, 22, 23, 32, 33, 34, 56, 98, 123, 298 ]
}
sort(array)
优化前的时间复杂度是15²=225，优化后的时间复杂度为123，少了一半。
选择排序（Selection Sort）
选择排序的原理是，从头开始循环去找最小或者最大的数，找到后与数组首位数交换。下一次则从下一个数字开始去查找最小的数，再次交换。其时间复杂度是(n-1)！。
const array = [10, 2, 23, 123, 12, 32, 34, 56, 1, 98, 11, 22, 33, 298, 4]
function sort (array) {
let result = [...[], ...array]
let count = 0
let minNumberIndex = 0
for (let i = 0; i < result.length; i++) {
minNumberIndex = i
for (let j = i + 1; j < result.length; j++) {
minNumberIndex = result[j] < result[minNumberIndex] ? j : minNumberIndex
count++
}
const minNumber = result[minNumberIndex]
const currentNumber = result[i]
result[minNumberIndex] = currentNumber
result[i] = minNumber
}
console.log('count', count) // ( 15 - 1 )! = 105
console.log(result) // [ 1, 2, 4, 10, 11, 12, 22, 23, 32, 33, 34, 56, 98, 123, 298 ]
}
sort(array)
插入排序（Insertion Sort）
插入排序简单的应用场景就是打扑克牌，从第二张牌开始，向前面的牌去一一比较，找到插入的位置后将其插入。
const array = [10, 2, 23, 123, 12, 32, 34, 56, 1, 98, 11, 22, 33, 298, 4]
function sort (array) {
let result = [...[], ...array]
let count = 0
for (let i = 1; i < result.length; i++) {
const current = result[i]
let j = i - 1
while (current < result[j] && j >= 0) {
result[j + 1] = result[j]
j--
count++
}
result[j + 1] = current
}
console.log('count', count) // 44
console.log(result) // [ 1, 2, 4, 10, 11, 12, 22, 23, 32, 33, 34, 56, 98, 123, 298 ]
}
sort(array)
