JS 实现排序算法

👁 2021-03-06

利用JS实现常见的四种排序算法

1 冒泡排序

重复访问数组元素，依次比较相邻两个元素，然后进行交换

function bubblingSort(arr){
    for(let i = 0; i < arr.length - 1; i++){
        for(let j = 0; j < arr.length - i - 1; j++){
            if(arr[j] > arr[j+1]){
                let temp = arr[j]
                arr[j] =arr[j+1]
                arr[j+1] = temp
            }
        }
    }
    return arr
}

console.log(bubblingSort([3,6,5,1,8,9,0,7,2]))

2 快速排序

1.首先选择一个基数作为中心轴（一般选取第一个元素）
2.将比基数小的数放在基数的左边
3.将比基数大的数放在基数右边
4.然后分别对左边子右序列重复前三步

function quickSort(arr){
    if(arr.length <= 1){
        return arr
    }
    let leftArr = [],rightArr = [],res = []
    for(let i = 1; i< arr.length;i++){
        if(arr[i]<arr[0]){
            leftArr.push(arr[i])
        }else {
            rightArr.push(arr[i])
        }
    }
    res = res.concat(quickSort(leftArr),arr[0],quickSort(rightArr))
    return res
}
console.log(quickSort([2,5,4,1,7,8,9,0,4,3]))

3 选择排序

拿当前值与他之后的值进行比较然后交换

function selectSort(arr){
    for(let i = 0; i< arr.length; i++){
        for(let j = i+1; j < arr.length; j++){
            if(arr[i]<arr[j]){
                let temp = arr[i]
                arr[i] = arr[j]
                arr[j] = temp
            }
        }
    }
    return arr
}
console.log(selectSort([2,5,4,7,8,1,0,6]))

4 插入排序

将未排序数据，对已排序数据序列从后向前扫描，找到对应的位置并插入。
算法描述：
（1）从第一个元素开始，该元素可以被认为已经被排序
（2）取出下一个元素，在已经排好序的序列中从后往前扫描
（3）直到找到小于或者等于该元素的位置
（4）将该位置后面的所有已排序的元素从后往前依次移一位
（5）将该元素插入到该位置
（6）重复步骤2~5

function insertSort(arr){
    for(let i = 1; i < arr.length; i++){
        let pre = i - 1,currentNum = arr[i]
        while(pre >= 0 && currentNum < arr[pre]){
            arr[pre+1] = arr[pre]
            pre--
        }
        arr[pre+1] = currentNum
    }
    return arr
}
console.log(insertSort([3,2,5,1,7,9,0]))