每天一点算法-冒泡排序 (Day3)

介绍

冒泡排序执行步骤（以升序为例，并假设有n个待排序数）：
1.对比前两个数据，如果第1个比第2个大则交换位置，否则原封不动；
2.接着对比第2、3个数，按照第1个步骤执行；
3.按第1个步骤一直到对比第n-1和第n和位置，此时第n个就是最大的数；
4.将剩下的n-1个数按照上面的步骤执行，得到第二大的数；
5.以此类推直到对比完最后剩下的两个数即可；
图示：

冒泡排序

例子

假设有一个待排序数组[77, 6, 37, 96, 34, 6, 14], js实现如下(升序)：

function sort( arr ){
    var result = [];
    var len = arr.length - 1;
    for(var i = 0; i< len; i++){
        for(var j = 0; j < len- i; j ++ ){
            if(!arr[j + 1]) continue;
            if(arr[j + 1] < arr[j]){ // 交换位置
                var med = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = med;
            }
        }
    }
    return arr;
}

sort([77, 6, 37, 96, 34, 6, 14]); // =>[6, 6, 14, 34, 37, 77, 96]

时间复杂度

可以看到运遍历次数为：(n-1) + (n-2) + (n-3) + ... + 1 = (n^2 - n)/2, 按照大O阶推导方法得时间复杂度为 O(n^2)

感谢阅读！欢迎关注！持续更新中...