JavaScript - 冒泡排序算法

本章介绍冒泡排序的各个阶段，并包含一个 JavaScript 实现。"排序"指的是按升序重新排列元素的过程。

冒泡排序算法

对于排序新手来说，冒泡排序是一个很好的起点。由于其算法与我们大脑通常认为的比较排序类似，因此它是最简单的排序技术之一。

使用冒泡排序时，会比较数组中相邻的元素，如果第一个元素大于第二个元素，则交换位置。这样，值最高的"气泡"就会排在最上面。

每次迭代结束时，最靠近右侧的部分通常都处于正确的顺序。重复该过程，直到每个元素都位于正确的位置。

现在让我们看看冒泡排序的具体作用 -

• 从数组中的第一个元素开始，并将其与当前元素进行比较。

• 如果数组的当前元素大于下一个元素，则交换它们。

• 如果当前元素小于当前元素，则直接转到下一个元素。

• 再次从步骤 1 继续。

冒泡排序演示

以下是冒泡排序的迭代过程 -

迭代 1: [8,3,7,1,5] -> [3,8,7,1,5] -> [3,7,8,1,5] -> [3,7,1,8,5] -> [3,7,1,5,8]
迭代 2: [3,7,1,5,8] -> [3,7,1,5,8] -> [3,1,7,5,8] -> [3,1,5,7,8]
迭代 3: [3,1,5,7,8] -> [1,3,5,7,8] -> [1,3,5,7,8]
迭代 4: [1,3,5,7,8] -> [1,3,5,7,8]
最终排序列表: [1,3,5,7,8]

用 JavaScript 实现冒泡排序

bubbleSort 函数的输入是数组 arr。它使用两个循环。外层循环对每个元素迭代最多 n-1 次，其中 n 是数组的长度。内层循环比较相邻元素，如果它们顺序错误，则交换它们。

swapped 标志用于优化排序。如果数组已经排序，并且在循环过程中没有进行交换，我们可以提前结束循环。

function bubbleSort(arr) {
   let n = arr.length;
   let swapped;
    
   for (let i = 0; i < n - 1; i++) {
      swapped = false;
        
      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;
         }
      }        
      // 如果没有元素被交换，则数组已经排序
      if (!swapped) break;
   }    
   return arr;
}
// 示例
let arr = [8, 3, 7, 1, 5];
console.log("已排序数组:", bubbleSort(arr));

输出

元素排序后，结果如下 -

已排序数组:[ 1, 3, 5, 7, 8 ]

另一种实现冒泡排序的方法

以下是另一种使用略微不同的结构在 JavaScript 中创建冒泡排序的方法 -

function bubbleSort(arr) {
   let n = arr.length;

   for (let i = n - 1; i > 0; i--) {
      for (let j = 0; j < i; j++) {
         // 比较相邻元素
         if (arr[j] > arr[j + 1]) {
            // 如果顺序错误则交换
            // 使用解构进行交换
            [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; 
         }
      }
   }    
   return arr;
}
// 示例
let arr = [8, 3, 7, 1, 5];
console.log("已排序数组:", bubbleSort(arr));

输出

这将产生以下结果 -

已排序数组:[ 1, 3, 5, 7, 8 ]

复杂度

在最坏情况和平均时间复杂度下，数组是逆序的，因此在这种情况下时间复杂度为 O(n²)。

在最优时间复杂度和理想情况下，数组的时间复杂度为 O(n)，并且已经排序。辅助空间为 O(1)。