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

感谢阅读！欢迎关注！持续升级中…