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]));

参考资料