每日一算法之冒泡排序

程序&＃61;数据结构&＃43;算法

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

好了&＃xff0c;开始进入主题吧&＃xff01;

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

js代码如下&＃xff1a;

class Arr {// 构造函数constructor(numElements) {// 存储的数据this.data &＃61; []// 记录数组下标this.index &＃61; 0// 生成数据的个数this.numElements &＃61; numElements// 初始化数组&＃xff0c;数组长度为numElements,值为0-9for(let i &＃61; 0; i 0 && i % 10 &＃61;&＃61; 0) {str &＃43;&＃61; &＃39;\n&＃39;}}return str}// 将前后数据交换&＃xff0c;用于之后的排序swap(arr, index1, index2) {let tmp &＃61; arr[index1]arr[index1] &＃61; arr[index2]arr[index2] &＃61; tmp}}

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

测试一下&＃xff1a;

const numElements &＃61; 100
const myNums &＃61; new Arr(numElements)
myNums.setData()
console.log(myNums.toString())

生成随机数据并按格式打印&＃xff1a;

好了&＃xff0c;一个新的数组类已经创建完毕&＃xff0c;接下来开始我们的冒泡排序了&＃xff01;

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

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

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

先来一个简单实例&＃xff1a;

5 1 4 3 2

排序步骤&＃xff1a;

1 4 3 2 5
1 3 2 4 5
1 2 3 4 5
至此&＃xff0c;排序完成

接下来在刚刚创建的类中添加冒泡排序的代码&＃xff1a;

sort() {for(let outer &＃61; this.data.length; outer > 1; outer--) {for(let inner &＃61; 0; inner this.data[inner&＃43;1]) {this.swap(this.data, inner, inner&＃43;1)}}}
}

测试代码&＃xff1a;

const numElements &＃61; 10
const myNums &＃61; new Arr(numElements)
myNums.setData()
console.log(myNums.toString())
myNums.sort()
console.log(myNums.toString())


结果&＃xff1a;

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

让我们加一个toString()吧&＃xff01;

sort() {for(let outer &＃61; this.data.length; outer > 1; outer--) {for(let inner &＃61; 0; inner this.data[inner&＃43;1]) {this.swap(this.data, inner, inner&＃43;1)}}console.log(this.toString())}}

结果&＃xff1a;

现在我们可以看到排序的具体过程了&＃xff01;

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

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

好了&＃xff0c;冒泡排序算法暂时分享到这&＃xff0c;后续更新其他算法&＃xff0c;求关注&＃xff01;