iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 7
0
自我挑戰組

計算機概論X30天系列 第 7

Day7: [演算法] 用JS實現冒泡排序

閱讀前,建議可以參考Day1:閱讀指南&為何選擇這個題目?

▌挑戰簡介

  • 題目:計算機概論X30天

  • 挑戰內容:連續30天紀錄計算機概論、離散數學、演算法、資料結構等課程,還有自己學習程式的心得體悟。

  • 本篇性質:本篇紀錄性質較重,沒有仔細的解釋,不適合認真閱讀但可以看後面的心得

▌用JS實現冒泡排序

熟悉演算法的人知道冒泡排序(Bubble Sort)的複雜度是O(n^2)

以下是我嘗試自己用JS寫出的冒泡排序。

var time = 0;

// 比較函數
function compare(a, b) {
    if (a < b) {
        return 1;
    } else return 0;
    // 不符合排序就return0
}

// 交換函數
function swap(list, a, b) {
    var ele = list[a];
    list[a] = list[b];
    list[b] = ele;

}

// 每一回合執行該函數
function bubbleoneround(list) {

    var sortornot = 1;
    for (var i = 0; i < list.length - 1; i++) {
        if (compare(list[i], list[i + 1]) == 0) {
            swap(list, i, i + 1)
            sortornot = 0;
            console.log(list)
            time++
        }
        // 最後一趟會完全是1
    }
    return sortornot;
}

// bubble函數
function bubblesort(list) {

    for (var i = 0; i < list.length - 1; i++) {
        var sortornot = bubbleoneround(list)
        if (sortornot == 1) {
            console.log(time)
            break;
        }

    }
}

var list = [5, 10, 9, 8, 7, 6, 5, 4, 1];
bubblesort(list) //[ 1, 4, 5, 5, 6, 7, 8, 9, 10 ]

▌心得

  • 如果用時間複雜度(time complexity)分析上面的程式,可以發現時間複雜度真的就是O(n^2),有興趣的可以嘗試自己分析看看。
  • 其實不需要自己寫排序,JS就有自己內建的sort排序函式,因此我其實只要三行就可以解決同樣的問題
list.sort(function (a, b) {
    return a - b
});

我實現冒泡排序,純粹是作為練習。但這給我的啟發就是閱讀真的很重要,我花了一小時寫了60行code才實現排序,但其實只要使用內建的3行code,10秒就可以解決同樣的問題。

我在Day4:[心得]工程師的三個重要能力提到,我覺得工程是最重要的其中一個能力就是閱讀

市面上早已經有許多現成的解決方案了,只要好好閱讀文件,這些問題一下就解決了。雖然實作也很重要,但是先學會理解、利用他人的程式碼,其實更高效、效果也好。

就如同,知名顧問公司麥肯錫(McKinsey)的宗旨是「不要重新造輪子」
這點心得,在我比較自己的練習成果還有內建函式時,也更有感覺。


上一篇
Day6:[演算法]演算法是什麼?讓數學王子高斯教你什麼是演算法
下一篇
Day8:[計算機概論]十進位和二進位的轉換
系列文
計算機概論X30天30

尚未有邦友留言

立即登入留言