冒泡排序

思路

需要遍歷 length - 1 次
每一次遍歷
都從后往前進(jìn)行比較，
相鄰的兩兩比較大小，小的向前浮動(dòng)
時(shí)間復(fù)雜度 O(n²)

function bubbleSort(target) {
    let temp = null

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

        console.log(`第 ${i + 1} 次排序`)
    }

    return target
}

console.log(bubbleSort([23, 32, 5, 72, 12, 1]))

運(yùn)行結(jié)果

缺點(diǎn)：

當(dāng)目標(biāo)對(duì)象是已經(jīng)排序好的數(shù)據(jù)
也需要進(jìn)行多次遍歷

console.log(bubbleSort([1, 2, 3, 4, 5, 6]))

運(yùn)行結(jié)果

優(yōu)化

定義一個(gè)布爾值
在遍歷每一次的時(shí)候，如果發(fā)生位置交換，就改變布爾值
當(dāng)這一次循環(huán)結(jié)束之后，判斷該布爾值是否變化
變化了則繼續(xù)下一次，沒(méi)變則退出

function bubbleSort(target) {
    let temp = null
    let flag = false

    for(let i = 0; i < target.length - 1; i++) {
        for(let j = target.length - 1; j > i; j--) {
            if (target[j] < target[j - 1]) {
                temp = target[j]
                target[j] = target[j - 1]
                target[j - 1] = temp
                flag = true
            }
        }

        console.log(`第 ${i + 1} 次排序`)
        if (!flag) break
    }

    return target
}

console.log(bubbleSort([1, 2, 3, 4, 5, 6]))

運(yùn)行結(jié)果

選擇排序

遍歷 length - 1 次
從左到右開(kāi)始找，每遍歷一次將最小值跟當(dāng)前遍歷的第一個(gè)元素交換
時(shí)間復(fù)雜度 O(n²)

function selctionSort(target) {
    for (let i = 0; i < target.length - 1; i++) {
        let min = target[i]
        let minIndex = i

        for (let j = i + 1; j < target.length; j++) {
            if (target[j] < min) {
                min = target[j]
                minIndex = j
            }
        }

        console.log(`第${i + 1}次循環(huán)`, target)
        // 減少循環(huán)次數(shù)
        if (minIndex === i) break
        target[minIndex] = target[i]
        target[i] = min
    }

    return target
}

console.log(selctionSort([23, 32, 5, 72, 12, 1]))
console.log(selctionSort([1, 2, 3, 4, 5, 6])) 

運(yùn)行結(jié)果

插入排序

遍歷 length - 1 次
從 i + 1 項(xiàng)開(kāi)始往前遍歷，兩兩比較小的往前移動(dòng)，
時(shí)間復(fù)雜度 O(n2)

function insertionSort(target) {
    let temp

    for (let i = 0; i < target.length - 1; i++) {

        for (let j = i + 1; j > 0; j--) {
            if (target[j] < target[j - 1]) {
                temp = target[j - 1]
                target[j - 1] = target[j]
                target[j] = temp
            } else {
                // 當(dāng)不小于已排序好的最大值時(shí)
                // 退出每次遍歷，進(jìn)行下一次
                break
            }
        }

        console.log(`第${i + 1}次循環(huán)`, target)
    }

    return target
}
console.log(insertionSort([23, 32, 5, 72, 12, 1]))

運(yùn)行結(jié)果

快速排序

/**
 參數(shù)說(shuō)明
 target 需要排序的目標(biāo)數(shù)組
 l  需要排序的起始項(xiàng)
 r  需要排序的終止項(xiàng)
 */
function quickSort(target, l, r) {
    if (l >= r) return

    let i = l; let j = r; let key = target[l];//選擇第一個(gè)數(shù)為key

    while (i < j) {

        while (i < j && target[j] >= key)//從右向左找第一個(gè)小于key的值
            j--;
        if (i < j) {
            target[i] = target[j];
            i++;
        }

        while (i < j && target[i] < key)//從左向右找第一個(gè)大于key的值
            i++;

        if (i < j) {
            target[j] = target[i];
            j--;
        }
    }
    //i == j
    target[i] = key;
    quickSort(target, l, i - 1);//遞歸調(diào)用
    quickSort(target, i + 1, r);//遞歸調(diào)用
    return target
}

console.log(quickSort([23, 32, 5, 72, 12, 1, 2], 0, 5))
console.log(quickSort([23, 32, 5, 72, 12, 1], 4, 5))

運(yùn)行結(jié)果

【筆記不易，如對(duì)您有幫助，請(qǐng)點(diǎn)贊，謝謝】