排序算法-冒泡排序

概述

冒泡排序是很多初学编程的程序员接触到的第一种排序算法,它也是所有排序算法中最简单的算法,但是它是众多排序算法中,排序效率最差的一个。

冒泡排序比较所有相邻的两个项,如果第一个比第二个大,则交换它们。元素项向上移动至正确的顺序,就好像气泡升至表面一样,冒泡排序因此得名。

冒泡排序全解析

假如有这样一组数值不等的数组,将天平放在数组序列的右端,并比较天平左右的数字。

在这种情况下,我们将比较7和6。

冒泡排序-图解过程1

比较后,如果两个树中,右边的数字较小,则交换这两个数字的位置。

因为6比7小,所以这两个数字要进行交换。

冒泡排序-图解过程2

比较完成后,天平往前左移一个位置。

再重复比较数字的操作

因为6大于4,所以不需要进行交换。

冒泡排序-图解过程3

比较完成后,天平再接着往前左移一个位置。

不断重复比较两个数字和天平往前左移一个位置的操作……

直到天平移动到左端。

冒泡排序-图解过程4

此时最左端的数字已经排序好了

冒泡排序-图解过程5

再将天平返回右端,重复之前相同的操作,对其他数组进行排序(忽略已经排序好的数字)

冒泡排序-图解过程6

每重复一轮相同的操作,左侧会有一个数字被排序好,直到所有数字都被排序。

冒泡排序-图解过程7

此时,这一组数值不等的数组,已经被排序完成。

代码实现冒泡排序

为方便排序时的相邻数字比较或交换,定义一些比较和交换用的常量和方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 比较用的常量对象(保证代码优雅)
export const Compare = {
LESS_THAN: -1, // 如果第一个元素小于第二个元素,它就返回-1
BIGGER_THAN: 1, // 如果第一个元素大于第二个元素,它就返回1
EQUALS: 0 // 如果元素有相同的引用,它就返回 0
};
// 比较用的方法
export function defaultCompare(a, b) {
// 如果元素有相同的引用,它就返回 0
if (a === b) {
return Compare.EQUALS;
}
// 如果第一个元素小于第二个元素,它就返回-1,否之返回1
return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
/**
* 交换函数
* @param {*} array 传入需要交换的数组(这里传入堆)
* @param {*} a 传入要交换的节点A
* @param {*} b 传入要交换的节点B
*/
export function swap(array, a, b) {
// ES5写法(性能较好)
/* const temp = array[a]; // 要交换数组中的两个值,我们需要一个辅助变量来复制要交换的第一个元素
array[a] = array[b]; // 然后,将第二个元素赋值到第一个元素的位置
array[b] = temp; */ // 最后,将复制的第一个元素的值覆盖到第二个元素的位置
// ES6写法(性能较差) https://bugzilla.mozilla.org/show_bug.cgi?id=1177319
[array[a], array[b]] = [array[b], array[a]];
}

实现冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* 冒泡排序
* 冒泡排序的基本思想是:每次比较两个相邻的元素,如果它们的顺序错误就把它们交换过来。
* @param {array} array 要进行排序的数组
* @param {function} compareFn // 比较用的方法,默认为defaultCompare
* @returns {array} 返回排序后的数组
*/
export function bubbleSort(array, compareFn = defaultCompare) {
const { length } = array; // 声明一个名为length的变量,用来存储数组的长度
for (let i = 0; i < length; i++) { // 外循环,冒泡排序每一趟只能确定将一个数归位,所以数组中的每一项都需要经过一轮排序,轮数和数组长度一致
// console.log('--- ');
for (let j = 0; j < length - 1; j++) { // 内循环,用当前项与下一项做比较,对n个数进行排序,只用进行n-1趟
// console.log('compare ' + array[j] + ' with ' + array[j + 1]);
if (compareFn(array[j], array[j + 1]) === Compare.BIGGER_THAN) { // 如果这两项顺序不对(当前项比下一项大)
// console.log('swap ' + array[j] + ' with ' + array[j + 1]);
swap(array, j, j + 1); // 则交换它们(位置为j+1的值将会被换置到位置j处)
}
}
}
// 返回排序后的数组
return array;
}

上述的冒泡排序算法,并没有忽略已经排序好的数字,导致对已经排序好的数字进行了较多无用的对比判断。

所以可以对算法进行改进,对比时忽略已经排序好的数字:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* 改进后的冒泡排序
* 冒泡排序的基本思想是:每次比较两个相邻的元素,如果它们的顺序错误就把它们交换过来。
* @param {array} array 要进行排序的数组
* @param {function} compareFn // 比较用的方法,默认为defaultCompare
* @returns {array} 返回排序后的数组
*/
export function modifiedBubbleSort(array, compareFn = defaultCompare) {
const { length } = array; // 声明一个名为length的变量,用来存储数组的长度
for (let i = 0; i < length; i++) { // 外循环,冒泡排序每一趟只能确定将一个数归位,所以数组中的每一项都需要经过一轮排序,轮数和数组长度一致
// console.log('--- ');
for (let j = 0; j < length - 1 - i; j++) { // 内循环,用当前项与下一项做比较,对n个数进行排序,只用进行n-1趟,再从内循环减去外循环中已跑过的轮数i(已跑过轮数的数已归位,无须再进行比较)
// console.log('compare ' + array[j] + ' with ' + array[j + 1]);
if (compareFn(array[j], array[j + 1]) === Compare.BIGGER_THAN) { // 如果这两项顺序不对(当前项比下一项大)
// console.log('swap ' + array[j] + ' with ' + array[j + 1]);
swap(array, j, j + 1); // 则交换它们(位置为j+1的值将会被换置到位置j处)
}
}
}
// 返回排序后的数组
return array;
}

排序算法-冒泡排序
https://sothx.com/2021/04/27/bubbleSort/
作者
Sothx
发布于
2021年4月27日
许可协议