每日一算法之冒泡排序

ygyooo 发布于2019-08-20 16:25 / 3271人阅读

摘要：冒泡排序算法是最慢的排序算法之一，但也是一种最容易实现的排序算法。虽然这个算法是正常运行了，但是执行过程，数据是如何变化的呢，让我们一探究竟，这也能让我们真正理解冒泡排序算法，而不是只记得代码。

程序=数据结构+算法

在金庸武侠小说里，绝世高手的武功都是外功和内功的结合，你不仅需要能耍出亮瞎眼的招式，还得有能让招式发挥出真正威力的内功；编程也是如此，我们在学习编程语言的语法、各种工具的使用的同时，应该要去好好学习数据结构和算法，了解一些底层的原理，这样才能功力深厚。

好了，开始进入主题吧！

对计算机存储的数据执行操作，排序是很常见的一种操作。一切按顺序来，多方便。
这里我们先创建一个数组类。使用ES6的语法（class），赶潮流嘛。

js代码如下：

class Arr {
      // 构造函数
      constructor(numElements) {
        // 存储的数据
        this.data = []
        // 记录数组下标
        this.index = 0
        // 生成数据的个数
        this.numElements = numElements
        // 初始化数组，数组长度为numElements,值为0-9
        for(let i = 0; i < numElements; i++) {
          this.data[i] = i
        }
      }
      // 重新设置数据，随机生成
      setData() {
        for(let i = 0; i < this.numElements; i++) {
          // 生成随机数据
          this.data[i] = Math.floor(Math.random() * (this.numElements + 1))
        }
      }
      // 将数据都置为0
      clear() {
        for(let i = 0; i < this.numElements; i++) {
          this.data[i] = 0
        }
      }
      // 插入数据
      insert(elements) {
        this.data[index++] = elements
      }
      // 将数据按格式读取出来
      toString() {
        // 将数组转为字符串
        let str = ""
        for(let i = 0; i < this.data.length; i++) {
          str += this.data[i] + " "
          if(i > 0 && i % 10 == 0) {
            str += "
"
          }
        }
        return str
      }
      // 将前后数据交换，用于之后的排序
      swap(arr, index1, index2) {
        let tmp = arr[index1]
        arr[index1] = arr[index2]
        arr[index2] = tmp
      }
    }

其中的setData()函数生成了存储在数组中的随机数字。Math.random()函数会生成[0,1)区间内的随机数字，然后我们将其再乘以(numElements + 1)，这样就能生成1-100的随机数字集合了。这才是我们需要的数据。

测试一下：

const numElements = 100
const myNums = new Arr(numElements)
myNums.setData()
console.log(myNums.toString())

生成随机数据并按格式打印：

好了，一个新的数组类已经创建完毕，接下来开始我们的冒泡排序了！

排序的核心思想是指对一组数据按照一定的顺序重新排列。重新排列时用到的技术是一组嵌套的for循环。外循环负责遍历数组的每一项，内循环负责比较元素。

冒泡排序算法是最慢的排序算法之一，但也是一种最容易实现的排序算法。

为什么叫冒泡排序呢，因为数据值就像气泡一样从数组的一端漂浮到另一端。假设正在将一组数字按照升序排序，较大的值会浮动到数组的右侧，而较小值会浮动到数组的左侧。因为该算法会多次在数组中移动，比较相邻的数据，如果左侧值大于右侧值则会将它们互换。

先来一个简单实例：

5 1 4 3 2

排序步骤：

1 4 3 2 5
1 3 2 4 5
1 2 3 4 5
至此，排序完成

接下来在刚刚创建的类中添加冒泡排序的代码：

sort() {
  for(let outer = this.data.length; outer > 1; outer--) {
    for(let inner = 0; inner < outer - 1; inner++) {
      if(this.data[inner] > this.data[inner+1]) {
         this.swap(this.data, inner, inner+1)
      }
    }
  }
}

测试代码：

const numElements = 10
const myNums = new Arr(numElements)
myNums.setData()
console.log(myNums.toString())
myNums.sort()
console.log(myNums.toString())

结果：

代码非常简短，就是嵌套for循环，然后比较前后大小。
虽然这个算法是正常运行了，但是执行过程，数据是如何变化的呢，让我们一探究竟，这也能让我们真正理解冒泡排序算法，而不是只记得代码。

让我们加一个toString()吧！

sort() {
        for(let outer = this.data.length; outer > 1; outer--) {
          for(let inner = 0; inner < outer - 1; inner++) {
            if(this.data[inner] > this.data[inner+1]) {
              this.swap(this.data, inner, inner+1)
            }
          }
          console.log(this.toString())
        }
      }

结果：

现在我们可以看到排序的具体过程了！

如何看代码的意思呢，我们拿[9,8,7,6,5,4,3,2,1,0]这个数组来说：

首先我们这里完全需要进行9次遍历，才能完全排好序。
我们先从数组的第一个值排起，需要比较9次
第一次 8，7，6，5，4，3，2，1，0，9 将9排到最后，现在不需要管9了，因为它是最大的，而且排到了最后，那么接下来就只需要比较8次了，再接着就是7，依次递减，直到为1，最后结束循环
7 6 5 4 3 2 1 0 8 9
6 5 4 3 2 1 0 7 8 9
5 4 3 2 1 0 6 7 8 9
4 3 2 1 0 5 6 7 8 9
3 2 1 0 4 5 6 7 8 9
2 1 0 3 4 5 6 7 8 9
1 0 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
就是如此，这是最坏的情况，而算法就应该考虑最坏的情况来编写，这样才能适应各种情况。

好了，冒泡排序算法暂时分享到这，后续更新其他算法，求关注！

GPU云服务器云服务器冒泡排序前端冒泡排序冒泡排序代码 js冒泡排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/82918.html

前端排序算法总结；前端面试题2.0；JavaScript异步编程

摘要：与异步编程按照维基百科上的解释独立于主控制流之外发生的事件就叫做异步。因为的存在，至少在被标准化的那一刻起，就支持异步编程了。然而异步编程真正发展壮大，的流行功不可没。在握手过程中，端点交换认证和密钥以建立或恢复安全会话。 1、前端排序算法总结排序算法可能是你学编程第一个学习的算法，还记得冒泡吗？当然，排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿，面试官在比较...

aaron 2019-08-01 17:38 评论0 收藏0
前端排序算法总结；前端面试题2.0；JavaScript异步编程

摘要：与异步编程按照维基百科上的解释独立于主控制流之外发生的事件就叫做异步。因为的存在，至少在被标准化的那一刻起，就支持异步编程了。然而异步编程真正发展壮大，的流行功不可没。在握手过程中，端点交换认证和密钥以建立或恢复安全会话。 1、前端排序算法总结排序算法可能是你学编程第一个学习的算法，还记得冒泡吗？当然，排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿，面试官在比较...

ARGUS 2019-08-21 16:43 评论0 收藏0
前端排序算法总结；前端面试题2.0；JavaScript异步编程

摘要：与异步编程按照维基百科上的解释独立于主控制流之外发生的事件就叫做异步。因为的存在，至少在被标准化的那一刻起，就支持异步编程了。然而异步编程真正发展壮大，的流行功不可没。在握手过程中，端点交换认证和密钥以建立或恢复安全会话。 1、前端排序算法总结排序算法可能是你学编程第一个学习的算法，还记得冒泡吗？当然，排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿，面试官在比较...

April 2019-08-30 15:53 评论0 收藏0
Java 数据结构与算法系列之冒泡排序

摘要：冒泡排序一种运行效率很低的排序算法，然而虽然排序效率低，确实排序入门很重的算法，因为冒泡排序的思路是最简单最容易理解的排序算法了。二冒泡排序定义冒泡排序是一种通过两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止的交换排序。一、前言相信大部分同学都已经学过数据结构与算法这门课了，并且我们可能都会发现一个现象就是我们所学过的数据结构与算法类的书籍基本都是使用 C 语言来...

1treeS 2019-08-15 17:40 评论0 收藏0
PHP排序算法之冒泡排序

摘要：一冒泡排序原理对一组数据，比较相邻数据的大小，将值小数据在前面，值大的数据放在后面。通过以上五轮排序，若干次比较，我们有理由推断出一个结论对于一个长度为的数组，我们需要排序轮，每轮要比较次。一、冒泡排序　　原理：对一组数据，比较相邻数据的大小，将值小数据在前面，值大的数据放在后面。（以下都是升序排列，即从小到大排列）　　举例说明： $arr = array(6, 3, 8,...

Raaabbit 2019-07-01 10:30 评论0 收藏0