冒泡排序
冒泡排序
基本概念
冒泡排序，英语叫做 Bubble Sort，这是所有排序方法中最为简单的排序方法，该排序算法的核心思想如下：
- 遍历整个元素序列，每次取出两个 相邻 的元素进行比较
- 如果顺序不对（看你具体的排序规则：如从大到小、首字母从 Z 到 A），就进行交换
- 一次遍历完成，称之为完成了一次冒泡。每一轮冒泡会确定一个数的正确位置
- 例如从小到大排序（升序），那么第一轮冒泡就会确定最大的数、第二轮冒泡就会确定倒数第二大的数，依此类推....
代码实现
function bubbleSort(arr) {
let n = arr.length;
let swapped = false; // 记录是否发生了交换
// 外层 for 循环控制的是冒泡的次数
for (let i = 0; i < n - 1; i++) {
// 内层循环控制的是比较的次数
// 因为比较是从第一个数字开始
for (let j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 进行交换
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
// 发生了交换，置 swapped 为 true
swapped = true;
}
}
// 出了内层for循环后，判断是否发生了交换
// 我们就需要判断是否进入过 if，如果没有进入过，说明数组已经有序
if (!swapped) {
break;
}
}
}
let arr = [5, 3, 8, 4, 2];
bubbleSort(arr);
console.log(arr);
复杂度
- 时间复杂度：
O(n^2) - 空间复杂度：因为只用到了一些循环和交换的辅助变量，这些变量的数量不会随着 n 的增加而增长，所以空间复杂度为
O(1)
稳定性
所谓稳定性，指的是 相同的元素 在排序后的相对顺序是否保持不变。如果保持不变，那就是稳定的，否则就是不稳定。
举例：
（value、id）
[(5, 1), (3, 2), (5, 3), (2, 4)]
如果使用稳定排序
[(2, 4), (3, 2), (5, 1), (5, 3)]
如果使用不稳定排序
[(2, 4), (3, 2), (5, 3), (5, 1)]
冒泡排序的核心原理是相邻的两个数进行比较，假设我们是升序排序，那么只有右边的数小于左边的时候，才会交换。相等的情况下是不会做操作的。因此冒泡排序是一种 稳定 的排序方式。
我的另外两种实现方式
function mySort(arr) {
let start = 0
let end = arr.length
while(end >= start) {
for(let i = 0; i < (end - start); i++) {
if(arr[i] < arr[i + 1]) {
let mid = arr[i + 1]
arr[i + 1] = arr[i]
arr[i] = mid
}
}
start ++
}
return arr
}
function forSort(arr) {
let end = arr.length
for(let i = 0; i + 1 < end; end--) {
for(let j = 0; j < end - 1; j++) {
if(arr[j] < arr[j + 1]) {
let mid = arr[j + 1]
arr[j + 1] = arr[j]
arr[j] = mid
}
}
}
return arr
}
console.log(forSort([7,2,5,2,1,7,6,2,0,67,3]))
-EOF-
冒泡排序
http://localhost:8090/archives/mou-pao-pai-xu