冒泡排序

冒泡排序是最简单的交换排序，冒泡排序基本原理：

对 N 个元素的待排序序列，共进行 N-1 次循环。
在第 k 次循环中，从第1到第 N-k 个元素从前往后进行比较，每次比较相邻的两个元素，若前一个元素比后一个大则交换两元素的位置，否则位置保持不变。
这样一次循环，就把第 k 大的元素放在了 N-k 的位置上，称为第 k 趟冒泡。整个过程共进行 N-1 趟，直到第 1 个元素和第 2 个元素比较完成，最终剩余最小的元素留在第一个位置，排序结束。

C 语言实现：

// 这里我们可以增加一个flag,如果一趟排序下来没有任何元素交换，说明序列是有序的，不需要继续进行下一次循环

void Swap(int *a, int* b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

void BubbleSort(int a[],int N){
    int i,j;
    int flag;
    for(i = N-1;i >= 0;i--){
        flag = 0;
        for(j = 0;j < i;j++){
            if(a[j] > a[j+1]){
                Swap(&a[j],&a[j+1]);
                flag = 1;
            }
        }
        // 全程无元素交换，退出循环
        if (!flag) {
            break;
        }
    }
}

JS语言实现：

function BubbleSort(a){
    let i,j;
    let flag;
    let N = a.length;
    for(i = N-1;i >= 0;i--){
        flag = 0;
        for(j = 0;j < i;j++){
            if(a[j] > a[j+1]){
                [a[j],a[j+1]] = [a[j+1],a[j]];
                flag = 1;
            }
        }
        // 全程无元素交换，退出循环
        if (!flag) {
            break;
        }
    }
}

很显然最坏情况下，冒泡排序的时间复杂度为 O(N²) ；在最好情况下，由于用了 flag 标记，只需要进行 O(N) 次比较就从循环中跳出来了。程序的平均时间复杂度为 O(N²)。