大师网-带你快速走向大师之路 解决你在学习过程中的疑惑,带你快速进入大师之门。节省时间,提升效率

每天一点算法-冒泡排序 (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)

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