Heading

冒泡排序的基本思想是：从后往前（或从前往后）两两比较相邻的元素，若为逆序则交换，直到序列比较完。称之为第一趟排序，结果是将最小的元素交换到待排序列的第一个位置，关键字最小的元素像气泡一样往上“漂浮”到“水面”。下一趟排序，前一趟确定的最小元素不再参与比较，每趟冒泡的结果是把序列中的最小元素放到了最终位置。这样n-1趟就排序完成。

点击查看代码

/**
 * 冒泡排序
 * @param {*} arr 
 * @param {*} n 
 */
export function BubbleSort(arr = [], n = 0) {
    let swapFlag;
    for (let i = 0; i < n; i++) {
        swapFlag = false;
        for (let j = 0; j <= n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swapFlag = true;
                Swap(arr, j, j + 1);
            }
        }
        if (!swapFlag) break;//本趟无交换说明已经有序
    }
    return arr;
}

性能分析如下：

• 空间效率：仅使用了常数个辅助单元，空间复杂度为O（1）。
• 时间效率：当初始序列有序时，第一趟不发生交换，直接跳出循环，比较次数为n-1，移动次数为0，从而最好的时间复杂度为O（n）；当初始序列逆序时，需要进行n-1趟排序，第i趟排序要进行n-i次关键字比较，每次比较必须移动元素3次完成交换。比较次数=（n-1 + n-2 +... +1）=n*(n-1)/2，移动次数=3*n*(n-1)/2，从而最坏的时间复杂度为O（n^2），平均时间复杂度也为O（n^2）。
• 稳定性：由于i>j且arr[i]=arr[j]时不会发生交换，因此冒泡排序是一种稳定的排序方法。