冒泡排序
冒泡排序的核心思路,就是每一轮都把最大的数”冒”到数组顶部.
1 算法过程
(从小到大排序)
1. 每一轮排序,都从第一个数开始,比较相邻的数;
2. 如果第一个数比第二个数大,则交换两个数的位置;
3. 如果第一个数不大于第二个数,则不交换位置,开始比较第二个数和第三个数;
4. 以此类推,直到比完最后两个数,选出数列最大值置于末尾;
5. 待排数列更新为原数列减去末尾值,开始下一轮排序,重复上面的步骤;
2 排序演示
对下面的数列进行冒泡排序:
3, 4, 1, 5, 2
第一轮排序开始,从第一个数3开始,比较相邻的数4
3, 4, 1, 5, 2
↑ ↑
3不大于4,不交换位置,开始比较第二个数4和第三个数1
3, 4, 1, 5, 2
↑ ↑
4大于1,交换位置,开始比较第三个数4和第四个数5
3, 1, 4, 5, 2
↑ ↑
4不大于5,不交换位置,开始比较第四个数5和最后一个数2
3, 1, 4, 5, 2
↑ ↑
5大于2,交换位置,此时5已到达数列末尾,第一轮排序结束,排序结果为:
3, 1, 4, 2, 5
第二轮排序开始,待排数列为
3, 1, 4, 2
(5已经确认为上一轮排序数列的最大值,不参与第二轮排序)
从第一个数3开始,比较相邻的数1
3, 1, 4, 2
↑ ↑
3大于1,交换位置,比较第二个数3和第三个数4
1, 3, 4, 2
↑ ↑
3不大于4,不交换位置,比较第三个数4和最后一个数2
1, 3, 4, 2
↑ ↑
4大于2,交换位置,此时4已到达数列末尾,第二轮排序结束,排序结果为
1, 3, 2, 4
第三轮排序开始,待排数列为
1, 3, 2
从第一个数1开始,比较相邻的数3
1, 3, 2
↑ ↑
1不大于3,不交换位置,比较第二个数3和最后一个数2
3大于2,交换位置,此时3已到达数列末尾,第三轮排序结束,排序结果为
1, 2, 3
第四轮排序开始,待排数列为
1，2
从第一个数1开始,比较最后一个数2
1, 2
↑ ↑
1不大于2,不交换位置,此时2已是数列末尾,第四轮排序结束,排序结果为
1, 2
第五轮排序,待排数列只剩一个数1,排序结束,得到有序数组
1, 2, 3, 4, 5
3 基本实现
const arr = [3, 2, 5, 1, 4, 6, 9, 10, 8, 7];
// 交换方法
function swap(arr, i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 冒泡排序
function bubbleSort() {
// 缓存数组长度
const len = arr.length;
// 外层循环:需要多少轮排序
for (let i = 0; i < len - 1; i++) {
// 内层循环:一轮排序下,遍历待排数列进行比较和交换
for (let j = 0; j < len - 1 - i; j++) {
// 前面的数大于后面的数,则交换
if (arr[j] > arr[j+1]) {
// [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
swap(arr, j, j+1)
}
}
}
return arr;
}
4 优化
实际上,在前面的基本实现中,即使是在最好的情况下(原数列本身就是有序数列),如[1,2,3,4,5],他也需要比较n(n-1)/2次,也就是说,在最好的情况下对应的时间复杂度为O(n^2).
但我们知道,实际上在冒泡排序中,最好的情况下,我们只需要比较(n-1)次,交换0次就可以了.也就是说,在最好的情况下对应的时间复杂度应该是O(n).
为此需要对代码进行改进,那怎么改进呢?
也许你已经发现,在前面排序演示中,第三轮排序后,我们已经得到了有序数列,从第四轮排序开始,是不会有交换记录的.
因此,我们可以在一轮排序中添加一个检测变量flag,初始化为false,只要这轮排序有交换记录,就将其置为true.
一轮排序下来,如果flag仍然为false,说明数列已经有序,直接return,不再进行后面的循环.
代码如下:
// 冒泡排序
function bubbleSort() {
// 缓存数组长度
const len = arr.length;
// 外层循环:需要多少轮排序
for (let i = 0; i < len - 1; i++) {
let flag = false;
// 内层循环:一轮排序下,遍历待排数列进行比较和交换
for (let j = 0; j < len - 1 - i; j++) {
// 前面的数大于后面的数,则交换
if (arr[j] > arr[j+1]) {
// [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
swap(arr, j, j+1);
flag = true;
}
}
// 如果一轮排序没有交换记录,直接返回有序数列
if (!flag) return arr;
}
return arr;
}
5 时间复杂度
- 最好情况下,原数列有序,只需比较
(n-1)次,交换0次,时间复杂度为O(n); - 最坏情况下,原数列逆序,需要比较和交换
n(n-1)/2次,时间复杂度为O(n^2); - 平均时间复杂度为
O(n^2).
6 稳定性
冒泡排序是通过不断的交换位置,将大的元素往后调(或把小的元素往前调).比较是发生在相邻两个元素之间,如果两个元素相等,不会进行交换.因此,冒泡排序是稳定的.