三种排序算法

May 07,2022

//冒泡排序:两两比,大的放后面,一轮过去,最大的排在了最后面,前面的再按这种方法比,直到从小到大排列

function bubble(arr,n) {
    for(let i = 0;i<n;i++) {
        if(arr[i]>arr[i+1]) {
            [arr[i],arr[i+1]] = [arr[i+1],arr[i]]
        }
    }
}

function bubbleSort(arr){
    for(let i = arr.length-1;i>0;i--){
        bubble(arr,i)
    }
    return arr
}

let bubbleArr = bubbleSort([0,5,3,8,9,6,5,11,15,7,4])
console.log('bubbleArr',bubbleArr)

/**
 * 选择排序:
 * 先假设第一个数是最大,如果后面找到比他大的,那个数就成为最大,再往后比,直到找到最大的数。
 * 找到的最大的数和最后一位交换位置。再在前面找最大的,放在倒数第二位。
 */

function selectMaxPos(arr,n){
    let max = arr[0]
    let pos = 0
    for(let i = 1;i<=n;i++){
        if(arr[i]>max) {
            max = arr[i]
            pos = i
        }
    }
    return pos
} 

function selectSort(arr){
    for(let i = arr.length-1;i>0;i--){
        let pos = selectMaxPos(arr,i)
        let temp = arr[i]
        arr[i] = arr[pos]
        arr[pos] = temp
    }
    return arr
}
let selectArr = selectSort([0,5,3,8,9,6,5,11,15,7,4])
console.log('selectArr',selectArr)

/**
 * 插入排序
 * 假设前面有一段已经排好序的序列,这个序列之后的第一位数和前面的比,如果前面的大,那么前面的往后移一位
 * 再和前面的比,大往后移,小则停止比较,把那个数填在那个位置即可
 */
function insert(arr,n){
    let i = n
    let key = arr[n]
    while(arr[i-1] > key){
        arr[i] = arr[i-1]
        i--
        if(i==0) {
            break
        }
    }
    arr[i] = key
}
function insertSort(arr) {
    for(let i = 1; i< arr.length; i++){
        insert(arr,i)
    }
    return arr
}
let insertArr = insertSort([0,5,3,8,9,6,5,11,15,7,4])
console.log('insertArr',insertArr)

上一篇 下一篇
Comments
Write a Comment