乐闻世界logo
搜索文章和话题
中文
JavaScript 实现冒泡排序算法

JavaScript 实现冒泡排序算法

乐闻的头像
乐闻

2022年03月24日 12:16· 阅读 517

前言

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

本文将介绍如何实现 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 实现中已经包含了这种优化。

标签: