Bubble sort 氣泡排序法

Bubble sort 氣泡排序法
Categories:
Tags:

複雜度

複雜度 Big O
最差時間複雜度 Worst-case time complexity Big O(n^2)
平均時間複雜度 Average-case time complexity Big theta (n^2)
最佳時間複雜度 Best-case time complexity Big omega (n)
空間複雜度 Space complexity Big O (1)

演算法

1. 比較首 2 個陣列元素，將數字較大元素放在右方

2. 右方元素持續與後方陣列元素比較，持續將數字較大元素放在右方

3. 最後最大的元素會在陣列最右方

4. 持續這個步驟，將剩餘的陣列元素做比較

持續地將最大元素比較放在右方，右方就會依序存放由大到小的數字

Bubble sort 氣泡排序法

程式

JavaScript

function bubbleSort(sortNumberList) {
    for (var finishCompareCount = 0; finishCompareCount < sortNumberList.length; finishCompareCount++) {
        // 設定比較完的元素數量，確保所有元素大小都比較完了
        // 最後要比較的元素索引：扣除已經比較完的元素 + 最後元素不需要再跟後方比較
        var finalCompareElementIndex = sortNumberList.length - finishCompareCount - 1;
        for (var compareIndex = 0; compareIndex < finalCompareElementIndex; compareIndex++) {
            // 從第一個元素開始比較，直到比到最後一個元素前
            var leftNumber = sortNumberList[compareIndex];
            var rightNumber = sortNumberList[compareIndex + 1];
            //Value comparison using ascending order
            if (leftNumber > rightNumber) {
                // 當「左方數字」比「右方數字」大，將兩個數字交換，大的數字放在右方
                [sortNumberList[compareIndex + 1],sortNumberList[compareIndex]] = [sortNumberList[compareIndex],sortNumberList[compareIndex + 1]];
            }
        }
    }
    // 已排序清單
    return sortNumberList;
}

console.log(bubbleSort([5, 3, 8, 4, 6]));

TypeScript

function bubbleSort(sortNumberList: number[]){
    for(let finishCompareCount = 0; finishCompareCount < sortNumberList.length; finishCompareCount++){
        // 設定比較完的元素數量，確保所有元素大小都比較完了
        // 最後要比較的元素索引：扣除已經比較完的元素 + 最後元素不需要再跟後方比較
        let finalCompareElementIndex = sortNumberList.length - finishCompareCount - 1;
        for(let compareIndex = 0; compareIndex < finalCompareElementIndex; compareIndex++){
            // 從第一個元素開始比較，直到比到最後一個元素前
            let leftNumber: number = sortNumberList[compareIndex];
            let rightNumber: number = sortNumberList[compareIndex + 1];

            if(leftNumber > rightNumber){
                // 當「左方數字」比「右方數字」大，將兩個數字交換，大的數字放在右方
                [sortNumberList[compareIndex + 1],sortNumberList[compareIndex]] = [sortNumberList[compareIndex],sortNumberList[compareIndex + 1]];
            }
        }
    }
    // 已排序清單
    return sortNumberList;
};

console.log(bubbleSort([5,3,8,4,6]));

參考資料