复习任意长度的数组排序
let sort = (numbers) => {
if(numbers.length > 2){
let index = minIndex(numbers)
let min = numbers[index]
numbers.splice(index, 1)
return [min].concat(sort(numbers)) }else{
return numbers[0]<numbers[1] ? numbers :
numbers.reverse()
}
}
所有递归都可以改写成循环
目前的minIndex
let minIndex = (numbers) => {
numbers.indexOf(min(numbers))
let min = (numbers) => {
return min(
[numbers[0], min(numbers.slice(1))]
)
}
写为循环
let minIndex = (numbers) => {
let index = 0
for(let i=1; i<numbers.length; i++){
if(numbers[i] < numbers[index]){
index = i
}
}
return index
}
选择排序
每次找到最小的数放前面，然后对后面的数做同样的事情
let swap = (array,i,j) => {
let temp = array[i]
array[i] = array[j]
array[j] = temp
}
let minIndex = (numbers) => {
let index = 0
for(let i=1;i<numbers.length;i++){
if(numbers[i] < numbers[index]){
index = i
}
}
return index
}
let sort = (numbers) => {
for(let i=0; i< numbers.length -1; i++){
let index = minIndex(numbers.slice(i))+i //为什么要加i，因为slice以后下标从0开始计，所以要把slice掉的下标加回来
if(index!==i){swap(numbers, index, i)}
}
return numbers
}
错误地实现 swap
let swap = (a, b) => {
let temp = a
a = b
b = temp
}
swap(numbers[1], numbers[2])
你会发现，numbers[1] 和 numbers[2] 的值原封不动
因为 a b 是简单类型，传参的时候会复制值
而正确的 swap 中的 numbers 是对象，传参复制地址
这是传值 V.S. 传址的区别
发现bug用console.log大法调试
let sort = (numbers) => {
for(let i=0; i< numbers.length -1; i++){
console.log(`----`) //这个log用于分割每一次循环
console.log(`i: ${i}`)
let index = minIndex(numbers.slice(i))+ i
console.log(`index: ${index}`)
console.log(`min: ${numbers[index]}`)
if(index!==i){
swap(numbers, index, i)
console.log(`swap ${index}: ${i}`)
console.log(numbers)
}
}
return numbers
}
快速排序
通俗的说就是以某某为基准，小的去前面，大的去后面
重复这段话，就能排序
let quickSort = arr => {
if (arr.length <= 1) { return arr }
let pivotIndex = Math.floor(arr.length / 2) //Math.floor向下取整
let pivot = arr.splice(pivotIndex, 1)[0] //为什么要写[0],如果不写返回的是被切掉的数组，所以提取数组中的第0个，才是我们需要的数字
let left = []
let right = []
for (let i =0; i < arr.length; i++){
if (arr[i] < pivot) { left.push(arr[i])
} else { right.push(arr[i]) }
}
return quickSort(left).concat(
[pivot], quickSort(right)
)
}
归并排序
例如有一个数组[12, 3, 7, 21, 5, 9, 4, 6]
分成左边一半排好序，右边一半排好序
然后把左右两边合并(merge)起来
就变成了[3, 7, 12, 21]和[4, 5, 6, 9]
再分别比较两个数组的第0项，最小的提出来排前面，再把剩余的数组合并继续比较第0项
let mergeSort = arr =>{
let k = arr.length
if(k===1){return arr}
let left = arr.slice(0, Math.floor(k/2))
let right = arr.slice(Math.floor(k/2))
return merge(mergeSort(left),mergeSort(right))
}
let merge = (a, b) => {
if (a.length === 0) return b
if (b.length === 0) return a
return a[0] > b[0] ?
[b[0]].concat(merge(a, b.slice(1))) :
[a[0]].concat(merge(a.slice(1), b))
}
计数排序
用一个哈希表作记录
发现数字 N 就记 N: 1，如果再次发现 N 就加1
最后把哈希表的 key 全部打出来，假设 N: m，那么 N 需要打印 m 次
let countSort = arr =>{
let hashTable = {}, max = 0, result = []
for(let i=0; i<arr.length; i++){
if(!(arr[i] in hashTable)){
hashTable[arr[i]] = 1
} else {
hashTable[arr[i]] += 1
}
if(arr[i] > max) {max = arr[i]}
}
for(let j=0; j<=max; j++){
if(j in hashTable){
for(let i =0; i<hashTable[j]; i++){
result.push(j)
}
}
}
return result
}
其他的排序算法
- 冒泡排序
https://visualgo.net/zh/sorting - 插入排序
https://visualgo.net/zh/sorting 点击 INS - 希尔排序
http://sorting.at/ 自己选择 Shell Sort - 基数排序
https://visualgo.net/zh/sorting 点击 RAD
