冒泡排序法

2019-03-31 23:38:01

Imgur

無時無刻都在想 code,滑 IG 也在看 code,最近看到這個冒泡排序,零散的時間就想一下看一下,後來自己嘗試練習一下。

let myArr = [3, 6, 9, 4, 5, 1, 0, 7, 8, 2]
const bubbleSort = (arr) => {
    let sorted = false
    while(!sorted) {
        sorted = true
        arr.forEach((item, i) => {
            if(item > arr[i + 1]) {
                arr[i] = arr[i + 1]
                arr[i + 1] = item
                sorted = false
            }
        });
    }
    return arr
}

let sorted = false: 設定一個 flag,表示排序未完成。 while(!sorted): 排序未完成的話會往下執行。 sorted = true: 這邊在設定一個變數,先表示已經排序過了。 然後用 forEach 執行排序,當每個 item 都比下一個元素小的話,就表示排序完成了,不會進入條件裡面,就會 return arr,跳出 while 迴圈。

後來發現照片中的 let len = arr.length - 1 沒有執行到,後來就嘗試用 for 寫寫看。

const bubbleSort = (arr) => {
    let len = arr.length - 1
    let sorted = false
    let tmp = 0
    // if(!sorted) {
        for(let i = 0; i < len; i++) {
            sorted = true
            // console.log('arr[i]', arr[i], 'arr[i+1]',  arr[i+1], 'tmp',  tmp)
            if(arr[i] > arr[i + 1]) {
                tmp = arr[i]
                arr[i] = arr[i + 1]
                arr[i + 1] = tmp
                // console.log('arr[i]', arr[i], 'arr[i+1]',  arr[i+1], 'tmp',  tmp)
                sorted = false
                if(!sorted) {
                    bubbleSort(arr)
                }
            }

            console.log('arr[i]', arr[i], 'arr[i+1]',  arr[i+1], 'tmp',  tmp)
            console.log('arr', arr)
            console.log(sorted)
        }
        console.log(sorted)
    // }
    console.log(sorted)
    return arr
}

寫完之後,一直覺得很奇怪,為什麼跑過一輪就停止執行了呢?後來才發現,原來根本就是我寫錯了,跟 while 迴圈超級不熟的我,非常習慣用 for 迴圈,所以一開始我就寫了 if,原因就是出在 if 只會判斷一次啊!

然後尋找原因的過程中,想到用了遞迴,然後莫名其妙解決了。

整理一下的程式碼。

const bubbleSort = (arr) => {
    let len = arr.length - 1
    let sorted = false
    let tmp = 0
    for(let i = 0; i < len; i++) {
        sorted = true
        if(arr[i] > arr[i + 1]) {
            tmp = arr[i]
            arr[i] = arr[i + 1]
            arr[i + 1] = tmp
            sorted = false
            if(!sorted) {
                bubbleSort(arr)
            }
        }
    }
    return arr
}
let sortedArr = bubbleSort(myArr)
console.log(sortedArr)

然後彷彿腦袋中的有幾根筋通了的我,很快的用原本想用方式完成了!


const bubbleSort = arr => {
    let len = arr.length - 1
    let sorted = false
    let tmp = 0
    while(!sorted) {
        sorted = true
        for(let i = 0; i < len; i++) {
            if(arr[i] > arr[i + 1]) {
                tmp = arr[i]
                arr[i] = arr[i + 1]
                arr[i + 1] = tmp
                sorted = false
            }
        }
    }
    return arr
}
let newArr = bubbleSort(myArr)
console.log(newArr)