美文网首页前端开发那些事儿
每日一算法:冒泡排序

每日一算法:冒泡排序

作者: lio_zero | 来源:发表于2021-05-08 20:36 被阅读0次

    冒泡排序是最糟糕的排序之一,但了解冒泡排序的工作原理对您来说很重要。主要原因是要理解它的功能,避免在代码中做任何与它有点相似的事情。

    工作原理

    比较相邻的元素。如果第一个比第二个大,就交换他们两个。

    对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。

    针对所有的元素重复以上的步骤,除了最后一个。

    持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

    numbers swapped

    JavaScript 实现

    使用冒泡排序算法对数字数组进行排序。

    • 声明一个变量,该变量 swapped 指示在当前迭代期间是否交换了任何值。

    • 使用展开运算符(...)克隆原始数组 arr

    • 使用 for 循环遍历克隆数组的元素,在最后一个元素之前终止。

    • 使用嵌套 for 循环在 0i 之间的数组段上进行迭代,交换任何相邻的乱序元素并将其设置 swappedtrue

    • 如果 swappedfalse 在迭代之后,则不需要更多更改,因此将返回克隆的数组。

    const bubbleSort = arr => {
      let swapped = false
      const a = [...arr]
      for (let i = 1; i < a.length - 1; i++) {
        swapped = false
        for (let j = 0; j < a.length - i; j++) {
          if (a[j + 1] < a[j]) {
            [a[j], a[j + 1]] = [a[j + 1], a[j]]
            swapped = true
          }
        }
        if (!swapped) return a
      }
      return a
    }
    
    bubbleSort([2, 1, 4, 3]) // [1, 2, 3, 4]
    

    此示例来自 30 seconds of code 的 bubbleSort

    相关文章

      网友评论

        本文标题:每日一算法:冒泡排序

        本文链接:https://www.haomeiwen.com/subject/nrjddltx.html