復(fù)習(xí)任意長度的數(shù)組排序
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()
}
}
所有遞歸都可以改寫成循環(huán)
目前的minIndex
let minIndex = (numbers) => {
numbers.indexOf(min(numbers))
let min = (numbers) => {
return min(
[numbers[0], min(numbers.slice(1))]
)
}
寫為循環(huán)
let minIndex = (numbers) => {
let index = 0
for(let i=1; i<numbers.length; i++){
if(numbers[i] < numbers[index]){
index = i
}
}
return index
}
選擇排序
每次找到最小的數(shù)放前面刻炒，然后對(duì)后面的數(shù)做同樣的事情
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，因?yàn)閟lice以后下標(biāo)從0開始計(jì)嫁审，所以要把slice掉的下標(biāo)加回來
if(index!==i){swap(numbers, index, i)}
}
return numbers
}
錯(cuò)誤地實(shí)現(xiàn) swap
let swap = (a, b) => {
let temp = a
a = b
b = temp
}
swap(numbers[1], numbers[2])
你會(huì)發(fā)現(xiàn)，numbers[1] 和 numbers[2] 的值原封不動(dòng)
因?yàn)?a b 是簡單類型，傳參的時(shí)候會(huì)復(fù)制值
而正確的 swap 中的 numbers 是對(duì)象，傳參復(fù)制地址
這是傳值 V.S. 傳址的區(qū)別
發(fā)現(xiàn)bug用console.log大法調(diào)試
let sort = (numbers) => {
for(let i=0; i< numbers.length -1; i++){
console.log(`----`) //這個(gè)log用于分割每一次循環(huán)
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
}
快速排序
通俗的說就是以某某為基準(zhǔn)翅萤，小的去前面，大的去后面
重復(fù)這段話腊满，就能排序
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],如果不寫返回的是被切掉的數(shù)組套么，所以提取數(shù)組中的第0個(gè)培己，才是我們需要的數(shù)字
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)
)
}
歸并排序
例如有一個(gè)數(shù)組[12, 3, 7, 21, 5, 9, 4, 6]
分成左邊一半排好序，右邊一半排好序
然后把左右兩邊合并(merge)起來
就變成了[3, 7, 12, 21]和[4, 5, 6, 9]
再分別比較兩個(gè)數(shù)組的第0項(xiàng)胚泌，最小的提出來排前面省咨，再把剩余的數(shù)組合并繼續(xù)比較第0項(xiàng)
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))
}
計(jì)數(shù)排序
用一個(gè)哈希表作記錄
發(fā)現(xiàn)數(shù)字 N 就記 N: 1，如果再次發(fā)現(xiàn) N 就加1
最后把哈希表的 key 全部打出來玷室，假設(shè) 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 點(diǎn)擊 INS - 希爾排序
http://sorting.at/ 自己選擇 Shell Sort - 基數(shù)排序
https://visualgo.net/zh/sorting 點(diǎn)擊 RAD
