JavaScript 实现冒泡排序算法

前言

冒泡排序是计算机科学中最简单的排序算法之一，它的基本思想是通过重复遍历待排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行直到不需要再交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

本文将介绍如何实现 JavaScript 中的冒泡排序。

实现步骤

一、理解冒泡排序

冒泡排序工作原理如下：

1. 比较相邻的两个元素，如果前一个比后一个大，就把它们两个调换位置。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

二、编写冒泡排序函数

javascript
function bubbleSort(arr) {
    let len = arr.length;
    let swapped;
    do {
        swapped = false;
        for (let i = 0; i < len - 1; i++) {
            // 比较相邻的两个元素
            if (arr[i] > arr[i + 1]) {
                // 如果顺序错误，则交换元素位置
                let temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                swapped = true;
            }
        }
        // 减少一次排序的长度
        len--;
    } while (swapped); // 如果没有发生交换，则已经排序完成
    return arr;
}

三、使用冒泡排序函数

javascript
// 创建一个数组来排序
let numbers = [64, 34, 25, 12, 22, 11, 90];
// 调用冒泡排序函数
let sortedNumbers = bubbleSort(numbers);
// 输出排序后的数组
console.log(sortedNumbers);

四、运行代码并验证结果

将上面的代码片段复制到你的 JavaScript 开发环境中，运行该代码。如果一切正确，你应该会在控制台看到排序后的数组，类似于：

plaintext
[11, 12, 22, 25, 34, 64, 90]

五、理解代码的复杂度

冒泡排序的时间复杂度是 O(n^2)，因为它需要对数组进行两次嵌套循环。尽管它不适合处理大数据集，但由于其算法结构简单，它是介绍排序算法概念的好例子。

优化思路

虽然基础的冒泡排序已经可以工作，但还可以进行一些优化。例如，如果在某一趟排序中没有发生任何交换，可以认为该数列已经排好序了，可以提前结束排序。我们的 JavaScript 实现中已经包含了这种优化。