- 冒泡排序
function bubbleSort(array){
const len = array.length
// 一共要進行的次數(shù)由外層循環(huán)決定
for(let i = 0 ; i <len ;i++){
// 內(nèi)層循環(huán)決定每一輪比較的次數(shù)，由于已經(jīng)完成i項，故j在length-1-i
for(let j = 0 ; j<len-1-i ;j++){
if(array[j]>array[j+1]){
[array[j],array[j+1]] = [array[j+1],array[j]]
}
}
}
console.log(array)
return array
}
const a = [5,3,4,6,9,7,1]
bubbleSort(a)//[1, 3, 4, 5, 6, 7, 9]
- 選擇排序
// 從待排序數(shù)據(jù)中尋找最小值，將其與序列最左邊的數(shù)字交換
function selectSort(array){
const len = array.length
let minIndex
for(let i = 0 ; i < len ; i++){
minIndex = i
for(let j = i ; j <len ;j++){
if(array[j]<array[minIndex]) minIndex = j
}
// 找到待排序序列中的最小值下標，如果該下標不是i，則交換兩者
if(i !== minIndex){
[array[i],array[minIndex]] = [array[minIndex],array[i]]
}
}
console.log(array)
return array
}
const a = [5,3,4,6,9,7,1]
selectSort(a)//[1, 3, 4, 5, 6, 7, 9]
- 插入排序
// 插入排序就是從右側(cè)未排序區(qū)域內(nèi)取一個數(shù)據(jù)，
// 然后將它插入到已排序區(qū)域內(nèi)合適的位置
function insertSort(array){
const len = array.length
for(let i = 1 ; i<len ; i++){
// 記錄比較值的下標
let j = i
// 記錄比較值
let temp = array[j]
// 循環(huán)操作,當比較值的前一項比他小時,讓前一項向后移,同時轉(zhuǎn)移下標,繼續(xù)操作
while(j>0&&array[j-1]>temp){
array[j] = array[j-1]
j--
}
// 退出while循環(huán)時,j剛好位于插入位置
array[j] = temp
}
console.log(array)
return array
}
const a = [5,3,4,6,9,7,1]
insertSort(a)//[1, 3, 4, 5, 6, 7, 9]
- 快速排序
// 快排的觀念是分治，選取一個只，將所有小于它的只放在左邊，大于他的值放在右邊
// 對于左邊和右邊的子集，同樣處理，直到子集只剩下一個元素
function quickSort(array){
const len = array.length
if(len<2) return array
const left = [] ,right = []
let pivotIndex = len/2|0
// 避免重復，先將當前值從數(shù)組中取出
let pivot = array.splice(pivotIndex,1)[0]
for(let val of array){
if(val < pivot){
left.push(val)
}else{
right.push(val)
}
}
return quickSort(left).concat([pivot],quickSort(right))
}
const a = [5,3,4,6,9,7,1]
console.log(quickSort(a))//[1, 3, 4, 5, 6, 7, 9]
- 歸并排序
// 分治 (nlogn)
function merge(left,right){
let arr = []
while(left.length&&right.length){
if(left[0]<right[0]){
arr.push(left.shift())
}else{
arr.push(right.shift())
}
}
return [...arr,...left,...right]
}
function mergeSort(array){
if(array.length < 2) return array
const mid = array.length/2 |0
const left = array.splice(0,mid)
return merge(mergeSort(left),mergeSort(array))
}
const a = [5,3,4,6,9,7,1]
console.log(mergeSort(a))//[1, 3, 4, 5, 6, 7, 9]
