图片来源：medium
排序是数据结构和算法中最重要的部分之一。排序算法有很多种，这是最简单的算法之一：冒泡排序。
排序算法是计算机科学的基础，而冒泡排序是最简单、最直观的排序算法之一。这篇文章将探讨冒泡排序的工作原理，分析其时间复杂度，并演练 javascript 实现。
在本系列中，我将分享使用 javascript 的完整排序算法数据结构和算法，并从冒泡排序开始。如果您喜欢并希望我通过示例分享完整的排序算法，请喜欢并关注我。它激励我为你们创建和准备内容。
什么是冒泡排序？
冒泡排序是一种简单的排序算法，它重复遍历列表，比较相邻元素（下一个元素），如果顺序错误则交换它们。重复此过程直到列表排序完成。该算法因其较小的元素“冒泡”到列表顶部而得名。
javascript 实现：
让我们深入代码看看冒泡排序是如何在 javascript 中实现的：
// by default ascending orderfunction bubble_sort(array) { const len = array.length; // get the length of an array //the outer loop controls the inner loop, which means the outer loop will decide how many times the inner loop will be run. //if the length is n then the outer loop runs n-1 times. for (let i = 0; i len - i -1; j++) { // checking if the first element greater than to the next element if (array[j] > array[j + 1]) { // then, swap the value array[j] to array[j+1] let temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } return array; // return the sorted array;}const array = [7, 12, 9, 11, 3]; // input dataconsole.log(bubble_sort(array));// output data after sorted!// [3, 7, 9, 11, 12];
输出
按降序排序：
// descending orderfunction bubble_sort_descending_order(array) { const len = array.length; for (let i = 0; i < len - 1; i++) { for (let j = 0; j < len - i -1; j++) { // checking if first element greter than next element, if (array[j] < array[j + 1]) { // then, swap the value array[j] to array[j+1] let temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } return array;}const array = [7, 12, 9, 11, 3]; // input dataconsole.log(bubble_sort_descending_order(array));// output data after sorted!// [ 12, 11, 9, 7, 3 ]
输出：
已经添加了注释并解释了上面的每一行代码。但我也会详细解释，以帮助您理解完整的流程和代码。
工作原理：
初始化：我们首先确定数组的长度，这有助于控制迭代次数。外循环：该循环运行 n-1 次，其中 n 是数组的长度。每次迭代都会确保下一个最大元素被放置在正确的位置。内循环：对于外循环的每一次循环，内循环都会比较相邻元素，如果它们无序，则交换它们。内部循环的范围随着每次传递而减小，因为最大的元素已经排序在数组的末尾。交换：如果一个元素大于下一个元素，则使用临时变量交换它们。返回：最后返回排序后的数组。
优化版本：
// optimized version:function bubble_sort(array) { const len = array.length; // get the length of the array //the outer loop controls the inner loop, which means the outer loop will decide how many times the inner loop will be run. //if the length is n then the outer loop run n-1 times. for (let i = 0; i < len - 1; i++) { // inner loop will run based on the outer loop and compare the value, //if the first value is higher than the next value then swap it, loop must go on for each lowest value let isswapped = false; for (let j = 0; j array[j + 1]) { // then, swap the value array[j] to array[j+1] let temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; isswapped = true; } } //if no element swap by inner loop then break; if (isswapped === false) { break; } } return array;}const array = [7, 12, 9, 11, 3]; // input dataconsole.log(bubble_sort(array));// output data after sorted!// [3, 7, 9, 11, 12];
说明：
for (令 i = 0; i 让 isswapped = false布尔变量 isswapped 被初始化为 false。该变量用于跟踪在内部循环的当前传递期间是否交换了任何元素。如果没有发生交换，则数组已经排序，算法可以提前终止。for (让 j = 0; j if (数组[j] > 数组[j 1]) {此条件检查当前元素是否大于下一个元素。如果为 true，则需要进行交换才能正确排序元素。
let temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; isswapped = true;
这些行使用临时变量 temp 执行元素 array[j] 和 array[j 1] 的交换。交换后，isswapped 设置为 true，表示发生了交换。
if (isSwapped === false) { break; }
内部循环完成后，此条件检查 isswapped 是否仍然为 false。如果没有进行交换，则数组已经排序，并且可以使用break提前退出外循环。最后返回排序后的数组。
时间复杂度
在最坏和平均情况下，冒泡排序的时间复杂度为 (o(n²))，其中 (n) 是数组中元素的数量。这是因为每个元素都会与其他元素进行比较。在最好的情况下，当数组已经排序时，如果添加优化以在不需要交换时停止算法，时间复杂度可以是 (o(n))。
在最好的情况下，当数组已经排序时，由于 isswapped 优化，算法可以提前终止，导致时间复杂度为 (o(n))。
总体而言，由于其二次时间复杂度，冒泡排序对于大型数据集效率不高，但对于小型数组或作为理解排序算法的教育工具可能很有用。
结论
冒泡排序由于其简单性而成为一种用于教育目的的优秀算法。然而，由于其二次时间复杂度，它不适合大型数据集。尽管冒泡排序效率低下，但理解冒泡排序为学习更高级的排序算法奠定了基础。
以上就是了解冒泡排序算法：分步指南的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1499945.html
微信扫一扫 
支付宝扫一扫 
