冒泡排序、选择排序、插入排序、快速排序 、归并排序的JavaScript实现

1. 冒泡排序

function bubbleSort(array){
    const len = array.length
    // 一共要进行的次数由外层循环决定
    for(let i = 0 ; i <len ;i++){
        // 内层循环决定每一轮比较的次数，由于已经完成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]

2. 选择排序

// 从待排序数据中寻找最小值，将其与序列最左边的数字交换
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]

3. 插入排序

// 插入排序就是从右侧未排序区域内取一个数据，
// 然后将它插入到已排序区域内合适的位置
function insertSort(array){
    const len = array.length
    for(let i = 1 ; i<len ; i++){
        // 记录比较值的下标
        let j = i 
        // 记录比较值
        let temp = array[j]
        // 循环操作,当比较值的前一项比他小时,让前一项向后移,同时转移下标,继续操作
        while(j>0&&array[j-1]>temp){
            array[j] = array[j-1]
            j--
        }
        // 退出while循环时,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]

4. 快速排序

// 快排的观念是分治，选取一个只，将所有小于它的只放在左边，大于他的值放在右边
// 对于左边和右边的子集，同样处理，直到子集只剩下一个元素
function quickSort(array){
    const len = array.length
    if(len<2) return array
    const left = [] ,right = []
    let pivotIndex = len/2|0
    // 避免重复，先将当前值从数组中取出
    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]

5. 归并排序

// 分治 (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]