·6 分钟阅读·管理员
排序算法-冒泡排序
冒泡排序(Bubble Sort)是一种简单的排序算法。它**重复地遍历**要排序的数列,一次比较两个元素,如果达到某个条件就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
冒泡排序
排序算法-冒泡排序
冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果达到某个条件就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
冒泡排序的基本步骤:
- 比较相邻的元素:如果第一个比第二个大(升序排序),就交换它们两个。
- 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤,除了最后一个。
- 重复步骤1~3,直到排序完成。在某次遍历过程中如果没有发生任何交换,则说明列表已经完全排序,可以提前终止。
动画模拟:

冒泡排序的实现:
冒泡排序示例:
-
首先进行外层循环
-
然后内层循环遍历比较下一个元素,如果当前元素比下一个元素大,需要将这两个元素的位置交换
-
位置交换可以使用临时变量,也可以使用数组的解构方式,或者可以使用两个元素的运算方法:
比如有
a=1,b=3,需要交换位置,可以使用公式,a=a+b;b=a-b;a=a-ba=a+b>1+3=4b=a-b>a-3=1a=a-b=>4-1=3
javascript
/**
* @param arr{Array}
*/
const bubbleSort = (arr)=> {
for (let i = 0; i < arr.length; i++) {
// 这里-i主要是因为外层循环已经将最大的值放到了最后一个,此时的i代表的是,外层循环的次数,这样可以减少遍历次数
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j+1]) {
// 如果不用临时变量进行交换
/**
* a=1,b=3
* a=a+b
* b=a-b
* a=a-b
* a=1+3
* b=4-3=1
* a=4-1=3
*/
// arr[j] = arr[j] + arr[j+1];
// arr[j+1] = arr[j] - arr[j+1];
// arr[j] = arr[j] - arr[j+1];
// 使用临时变量交换
// const temp = arr[j+1];
// arr[j+1] = arr[j];
// arr[j] = temp;
// 使用数组方式交换
[arr[j], arr[j+1]] = [arr[j+1], arr[j]] ;
}
}
}
return arr
}
console.log(bubbleSort([34, 10, 64, 51, 32, 21])); // 输出: [10, 21, 32, 34, 51, 64]
console.log(bubbleSort([5, 1, 4, 2, 8])); // 输出: [1, 2, 4, 5, 8]
console.log(bubbleSort([])); // 输出: []
console.log(bubbleSort([1])); // 输出: [1]
console.log(bubbleSort([9, 7, 7, 3, 1, 2, 4])); // 输出: [1, 2, 3, 4, 7, 7, 9]
解释:
- 外层循环:最外层 循环用于控制整个排序过程,直至最后一个元素。
- 内层循环:每次遍历数组,比较相邻的元素并根据需要进行交换。在每一次完整的遍历之后,最大的未排序元素会被移动到最后的位置。
优化:
- 在上面的代码中,如果内层循环已经比较完成了或者原数组本身已经是排序好的,那么外层再次循环遍历的话,会增加遍历次数
- 比如:[1, 2, 3, 4, 7, 7, 9]此时,是不需要排序的,因此我们需要添加一个
isDone标志是否已经排序完成,如果内层循环没有进行比较,说明已经是排序好了,直接终止循环
javascript
/**
* @param arr{Array}
*/
const bubbleSort = (arr)=> {
for (let i = 0; i < arr.length; i++) {
let isDone = true // 默认完成的排序
// 这里-i主要是因为外层循环已经将最大的值放到了最后一个,此时的i代表的是,外层循环的次数,这样可以减少遍历次数
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j+1]) {
// 如果不用临时变量进行交换
/**
* a=1,b=3
* a=a+b
* b=a-b
* a=a-b
* a=1+3
* b=4-3=1
* a=4-1=3
*/
// arr[j] = arr[j] + arr[j+1];
// arr[j+1] = arr[j] - arr[j+1];
// arr[j] = arr[j] - arr[j+1];
// 使用临时变量交换
// const temp = arr[j+1];
// arr[j+1] = arr[j];
// arr[j] = temp;
// 使用数组方式交换
[arr[j], arr[j+1]] = [arr[j+1], arr[j]] ;
// 有交换,说明没有排序好
isDone = false
}
}
// 如果已经是排序好的,就中断循环
if (isDone){
break
}
}
return arr
}
时间复杂度分析:
- 最好情况:如果输入的数组已经是有序的,则冒泡排序只需要遍历一次数组,时间复杂度为 O(n)。
- 最坏情况:如果输入的数组是逆序的,则每次遍历都需要进行 n-i 次交换,总交换次数为 n*(n-1)/2,时间复杂度为 O(n^2)。
- 平均情况:冒泡排序的平均时间复杂度也是 O(n^2)。
尽管冒泡排序的概念简单且易于实现,但由于其时间复杂度较高,它通常不适用于大规模数据集的排序。在实际应用中,通常会选择更高效的排序算法,如快速排序、归并排序等。