简介
冒泡排序是一种较简单排序算法。它重复地走访过要排序的元素列,依次比较和交换两个相邻的元素,每一次遍历会将一个元素“浮”到数列的顶端,所以命名为冒泡排序
。
排序过程
对于数组[5, 10, 13, 15, 10, 100, 78, 46]
,要求从小到大排序。
- 从下标为j开始,比较相邻两个元素,如果arr[j] > arr[j + 1],则交换元素。
- 然后j++,比较下一对元素。重复上一步操作,直到这一次遍历结束。
- 从数组开始,重复1、2操作。
- 结束的时候,数组变成有序的数组。
js代码如下
var array = [5, 10, 13, 15, 10, 100, 78, 46];
function bubbing(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - 1; j++) {
if (arr[j] > arr[j + 1]) {
const temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
console.log(arr);
}
bubbing(array);
时间复杂度
长度为n的数组,假设冒泡排序时遇到最坏的情况,数组是反序的。每一趟需要交换 n - i
次。那么总共需要交换次数C为:
C = n – 1 + n – 2 + …… + 1
根据高斯求和公式可得:
C = n * (n – 1) / 2
那么冒泡排序的时间复杂度为:O(n²)
但是经过优化的冒泡排序可以在最好的情况,时间复杂度为O(n),下面第二次优化会讲。
优化
第一次优化
由于每次都会把一个最大或最小的元素排列到该去的位置,所以下一次遍历的时候就可以不遍历已有序的部分。
function bubbing_2(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
const temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
console.log(arr);
}
bubbing_2(array);
第二次优化
第一次优化减少了要遍历的次数,第二次优化则是加了一个岗哨。每一次遍历的时候判断是否发生过元素交换操作,如果没有没有发生,那就说明数组已经有序,则终止排序。
当数组本身就是有序的时候,只是遍历了一次,没有经过交换就完成排序。时间负责度为O(n)。
function bubbing_2(arr) {
for (let i = 0; i < arr.length; i++) {
let count = 0;
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
const temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
count++;
}
}
if (count == 0) break;
}
console.log(arr);
}
bubbing_2(array);
第三次优化
第三次优化的思路是从数组的两头分别进行冒泡操作,假如要从小到大排序。那正向就是将最小的元素放到末尾,反向就是将最大的元素放到头部。这种方案又称为鸡尾酒排序、来回排序
鸡尾酒排序的方式并不会减少交换元素的次数,这点非常重要。它对性能的优化在于某些情况下,遍历的次数会减少。
例如:数组[2, 3, 4, 1]
,需要经过4次外层遍历才能有序。而用鸡尾酒排序的思路,外层只需要一次即可。
function bubbing_3(arr) {
const len = arr.length;
const loop = Math.floor((len + 1) / 2);
// 既然每次都将两个元素排列到对的地方,
// 那外层的遍历次数就可以减少为原来的一半
for (let i = 0; i < loop; i++) {
let count = 0;
for (let j = i + 1; j < len - 1; j++) {
if (arr[j] > arr[j + 1]) {
const temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
count++;
}
}
for (let k = len - i - 1; k > 0; k--) {
if (arr[k] < arr[k - 1]) {
const temp = arr[k];
arr[k] = arr[k - 1];
arr[k - 1] = temp;
count++;
}
}
if (count == 0) break;
}
console.log(arr);
}
bubbing_3(array);
思考
冒泡排序是最基础的排序方式了,和交换排序、插入排序一样,思路简单,容易掌握。所以我一开始把冒泡排序写成交换排序,尴尬!
思考的问题有两点:
- 在鸡尾酒排序的方案中,仔细思考到底是哪里提升性能的时候,走了一个误区。以为交换次数会变少,其实不是。
- 鸡尾酒排序方案开始外层写的是循环到n结束,后来想到是从两头开始排序的,一次两个,岂不是可以减少外层次数,然后想了一下果然可以。(其实前面三段代码中外层的n都可以写成n – 1)
今天的文章冒泡排序时间复杂度怎么算_数据结构时间复杂度例题详解分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/74572.html