JS排序之冒泡排序详解

简介

冒泡排序是最基本，也是最容易实现的排序算法之一。它的基本思想是通过多次循环遍历数组，每次比较相邻两个元素的大小，如果发现顺序不对，就交换它们的位置，通过多次遍历和交换的操作，最终使得整个数组变得有序。

基本思路

1. 遍历数组，将相邻元素的大小进行比较，如果前面元素大于后面元素，则交换它们的位置；
2. 继续以相同的方式遍历数组，直到数组中的每个元素都已参加了比较。

算法分析

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

代码实现

function bubbleSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len; i++) {
    for (var j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        var temp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}

示例解析

示例1：从小到大排序

var arr = [3, 1, 4, 2, 5];
console.log(bubbleSort(arr)); // 输出 [1, 2, 3, 4, 5]

• 初始状态：[3, 1, 4, 2, 5]
• 第一轮遍历，第一次比较：[1, 3, 4, 2, 5]
• 第一轮遍历，第二次比较：[1, 3, 4, 2, 5]
• 第一轮遍历，第三次比较：[1, 3, 2, 4, 5]
• 第一轮遍历，第四次比较：[1, 3, 2, 4, 5]
• 第二轮遍历，第一次比较：[1, 2, 3, 4, 5]
• 第二轮遍历，第二次比较：[1, 2, 3, 4, 5]
• 第二轮遍历，第三次比较：[1, 2, 3, 4, 5]
• 第二轮遍历，第四次比较：[1, 2, 3, 4, 5]
• 第三轮遍历，第一次比较：[1, 2, 3, 4, 5]
• 第三轮遍历，第二次比较：[1, 2, 3, 4, 5]
• 第三轮遍历，第三次比较：[1, 2, 3, 4, 5]
• 第四轮遍历，第一次比较：[1, 2, 3, 4, 5]
• 第四轮遍历，第二次比较：[1, 2, 3, 4, 5]
• 第五轮遍历，无需比较，已排序完成。

示例2：从大到小排序

var arr = [3, 1, 4, 2, 5];
function bubbleSortDesc(arr) {
  var len = arr.length;
  for (var i = 0; i < len; i++) {
    for (var j = 0; j < len - 1 - i; j++) {
      if (arr[j] < arr[j + 1]) {
        var temp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}
console.log(bubbleSortDesc(arr)); // 输出 [5, 4, 3, 2, 1]

• 初始状态：[3, 1, 4, 2, 5]
• 第一轮遍历，第一次比较：[3, 4, 1, 2, 5]
• 第一轮遍历，第二次比较：[3, 4, 2, 1, 5]
• 第一轮遍历，第三次比较：[3, 4, 2, 1, 5]
• 第一轮遍历，第四次比较：[3, 4, 2, 1, 5]
• 第二轮遍历，第一次比较：[3, 2, 4, 1, 5]
• 第二轮遍历，第二次比较：[3, 2, 4, 1, 5]
• 第二轮遍历，第三次比较：[3, 4, 2, 1, 5]
• 第三轮遍历，第一次比较：[2, 3, 4, 1, 5]
• 第三轮遍历，第二次比较：[3, 2, 4, 1, 5]
• 第四轮遍历，第一次比较：[2, 3, 1, 4, 5]
• 第五轮遍历，第一次比较：[2, 1, 3, 4, 5]
• 第六轮遍历，第一次比较：[1, 2, 3, 4, 5]
• 第六轮遍历，无需比较，已排序完成。

从两个示例中可以看出，冒泡排序可以根据需求进行升序或者降序排列，但是无论是哪种排序方式，其都具有时间复杂度为O(n^2)的问题，对于大规模的数据进行排序时，效率较低，需要使用其他效率更高的排序算法。