冒泡排序是最基本的排序算法，是学习算法的入门英雄，就像是王者荣耀中的妲己和后羿。通过对冒泡排序的学习和代码实现，引出排序算法的原理和使用场景。
1、冒泡排序的实现原理
从前向后比较相邻的元素。如果前面元素比后面元素大，就交换他们的位置。重复执行此操作直到数列有序，举个例子：如图1-1
图 1-1
原始列表数据 list = [19, 14, 10, 4, 15, 26, 20, 96];
第一次比较：默认最大数是数列第一个数 19
19 > 14，19 和 14 交互位置，数据排序为：14，19，10，4，15，26，20，96
19 > 10，19 和 10 交互位置，数据排序为：14，10，19，4，15，26，20，96
19 > 4，19 和 4 交互位置，数据排序为：14，10，4，19，15，26，20，96
19 > 15，19 和 15 交互位置，数据排序为：14，10，4，15，19，26，20，96
19 < 26，19 不和 26 交互位置，数据排序为：14，10，4，15，19，26，20，96，由于26 > 19，此时的最大数变为了26，继续向后比较
26 > 20，26 和 20 交互位置，数据排序为：14，10，4，15，19，20，26，96
26 < 96，26 不和 96 交互位置，数据排序为：14，10，4，15，19，20，26，96，最大数为96，排在最后一位
第二次比较：默认最大数是数列第一个数 14，由于96已经是经过排序的最大值，不需要再参与排序，所以第二次只需要排序14，10，4，15，19，20，26数列，依次类推，直到所有数据都被排序
2、代码实现
let count = 0; // 记录一下遍历的次数
const list = [19, 14, 10, 4, 15, 26, 20, 96];
function bubbleSort (list) {
// 获取数组的长度
const length = list.length;
// 如果数据长度小于2，是没有必要排序的
if (length > 2) {
for (let i = 0; i < length; i++) {
// 为什么是 length - i -1呢？由于每次会排序一个最大值，不需要再参与排序，所以每次都需要减去已排序的数据个数
for (let j = 0; j < length - i -1; j++) {
if (list[j] > list[j + 1]) { // 如果前面元素比后面元素大，就交换他们的位置
const temp = list[j + 1];
list[j + 1] = list[j];
list[j] = temp;
}
count++;
}
}
return list;
}
return list;
}
执行结果：list = [ 4, 10, 14, 15, 19, 20, 26, 96 ]； 执行次数：count = 28；
3、排序优化
在上面的例子中，完成了冒泡排序的代码实现，如果仔细观察每次的排序结果会发现在第3次排序结束后数据已经完成了正确的排列顺序，但是排序依然进行直到所有的数据都被排序完成，如图3-1
图 3-1
对于数据量比较小的列表来说，以目前的计算机配置在不优化排序算法的情况下对用户来说也是无感知的，但是对于大数据量的列表排序做优化却是很有必要的，毕竟不是一个数量级的，引用一条哲学名言：量变会导致质变
优化方案1：增加一个排序完成状态 finished = true，在每次排序时设置为true，如果有位置交换则 finished = false，每次排序完成后判断 finished 是否为 true，如果 finished === true 说明排序已经完成
优化代码：
let count = 0; // 记录一下遍历的次数
const list = [19, 14, 10, 4, 15, 26, 20, 96];
function bubbleSort(list) {
if (list.length > 1) {
const length = list.length;
for (let i = 0; i < length; i++) {
let finished = true; // 默认为 true
for (let j = 0; j < length - i -1; j++) {
const value = list[j];
if (value > list[j + 1]) {
finished = false; // 还有待排序的数据
const temp = list[j + 1];
list[j + 1] = value;
list[j] = temp;
}
count++;
if (finished) { // finished === true 排序完成
break;
}
}
}
return list;
}
return list;
}
执行结果：list = [ 4, 10, 14, 15, 19, 20, 26, 96 ]； 执行次数：count = 22；
优化之后的执行次数差 = 28 - 22 = 6，优化效率 21.43%
优化方案2：把元素交互的位置作为结束条件，如果数列是无序的，当元素排序时就会有前数大于后数情况也就是说会前数和后数要交互位置，此时替换的位置肯定是大于0的，但如果数列是有序的则不会交互位置，所以交互位置为0，如果交互位置为0则排序结束
优化代码：
let count = 0;
const list = [19, 14, 10, 4, 15, 26, 20, 96];
function bubbleSort(list) {
if (list.length > 1) {
const length = list.length;
let lastPos = length - 1; // 内部循环结束位置
for (let i = 0; i < length; i++) {
let pos = 0; // 默认替换位置为 0
for (let j = 0; j < lastPos; j++) {
const value = list[j];
if (value > list[j + 1]) {
const temp = list[j + 1];
list[j + 1] = value;
list[j] = temp;
pos = j; // 记录交互位置
}
count++;
}
// 更新内部循环结束位置，pos记录的是交互的位置，说明pos之后的数据已排序完成
lastPos = pos;
}
return list;
}
return list;
}
执行结果：list = [ 4, 10, 14, 15, 19, 20, 26, 96 ]； 执行次数：count = 13；
优化之后的执行次数差 = 28 - 13 = 15，优化效率 53.57%
总结：
1、明确循环结束的判断条件，方法1的结束条件是循环结束，所以是消耗性能的，方法2是通过是否有交互的位置作为判断条件，而方法3把元素交互的位置为0时作为结束条件
2、分析数据规律，写出高效的排序算法代码
网友评论