写在前面
排序算法是《数据结构与算法》中最基本的算法之一。
作为一个前端程序员，算法或许只在面试时会有所提及，日常工作中似乎用的并不多，但我们依然要重视算法，这不仅是为了面试时胸有成竹，更何况算法本身也有自己的魅力！！
这个系列的文章的初衷是为了总结一下前端程序员应该掌握的算法，尽管前文说不仅仅为了面试，但我们功利一点来看，我们学习算法的首要目的确实是为了应对面试，因此，这一个系列的文章，笔者会尽量写得通俗易懂，毕竟只有你完全理解了，面试时才能说得出来。
因此，这个系列的文章既适用于对算法感兴趣想要入门的同学，也适用于面向面试开发的同学。希望看到文章的小伙伴们能有所收获，这就是我最大的愿望了。
对于讲解所使用的语言，我会使用Javascript，原因不必过多阐述，前端入行的敲门砖。
废话不多说，Let's just jump right into it.
冒泡排序
选择排序可能是十大排序算法中最简单最基础的一个，它的思想很简单：对于一个数列，冒泡排序算法会重复遍历这个数列，每一次遍历，都会对两个相邻的元素进行比较，将两个数中较大的数放在后面，从第一对比较到最后一对。直到所有的元素以正确的顺序排列。
举个例子，对于数组 arr = [1, 4, 3, 5, 2] ，我们需要将它按从小到大的顺序重新排序：
arr = [1, 4, 3, 5, 2]
arr[0] = 1 与 arr[1] = 4进行比较，顺序是从小到大没有问题；
arr[1] = 4 与 arr[2] = 3进行比较，顺序不对，因此将这两个数交换位置；
arr[2] = 4 与 arr[3] = 5进行比较（注意此时arr[2]已经变为4了哦 ），顺序是从小到大没有问题；
arr[3] = 5 与 arr[4] = 2进行比较，顺序不对，因此将这两个数交换位置。
那么在第一轮遍历之后，我们的数组变为了：arr = [1, 3, 4, 2, 5] ，第一轮的目的是为了将数组中最大的元素放到数组末尾，大家多试几个例子就可以明显地感受到这一特点。
好，接下来进行第二轮遍历：
arr = [1, 3, 4, 2, 5]
arr[0] = 1 与 arr[1] = 3进行比较，顺序是从小到大没有问题；
arr[1] = 3 与 arr[2] = 4进行比较，顺序是从小到大没有问题；
arr[2] = 4 与 arr[3] = 2进行比较，顺序不对，因此将这两个数交换位置；
排序完成后的数组为 arr = [1, 3, 2, 4, 5] , 第二轮遍历和第一轮遍历相差不大，但似乎比第一轮少比较了一次，为什么呢？
这是因为在第一轮比较中，我们已经把数组的最大元素放在了最后，因此就不需要再进行无用的比较了。
第三轮遍历同样如此，在第二轮比较中，我们已经把数组第二大的元素放在了倒数第二位上，因此第三轮比较时就可以不用比较 arr[2] =2 与 arr[3] = 4了。
第三轮比较：
arr = [1, 3, 2, 4, 5]
arr[0] = 1 与 arr[1] = 3进行比较，顺序是从小到大没有问题；
arr[1] = 3 与 arr[2] = 2进行比较，顺序不对，因此将这两个数交换位置。
排序完成后的数组为arr = [1, 2, 3, 4, 5]，冒泡排序算法结束。
之所以叫这个算法为冒泡排序，有一个说法是因为每次比较相邻的两个元素，就像在水面上冒起一串串泡泡来一样，冒泡排序的发明者就以此命名了。
好了，我们来总结一下冒泡排序的特点：
特点一：每次比较相邻两个元素的大小
特点二：第n个数比较 n - 1 次
接下来我们来看一下冒泡排序的代码实现：
代码实现：
let arr = [1, 4, 3, 5, 2];
var bubbleSort = function(arr){
let len = arr.length;
//使用两层循环，第一层循环用于控制遍历数组的次数
//第二层循环用于规定在第一轮遍历数组后，每次遍历都要排除最后一个已经正确归位的元素
//每次循环都减去i，这样就减去了不需要遍历的元素
for(let i = 0; i < len - 1; i++){
for(let j = 0; j < len - 1 - i; j++){
//交换两个相邻的元素
if(arr[j] > arr[j + 1]){
let temp = arr[j + 1];
arr[j + 1] = arr [j];
arr[j] = temp;
}
}
}
return arr;
};
代码如上，因为我们要控制第一轮之后的遍历，要让每一轮都要减少一个已经正确归位的元素，因此，一个办法就是从第 i 轮循环开始每次都减少 i 个需要便利的元素，这就是第二层循环中 j 要小于 len - 1 - i 的原因。
接下来我们来看一下冒泡排序的空间复杂度与时间复杂度。
冒泡排序的空间复杂度与时间复杂度：
由于冒泡排序没有使用额外的存储空间，所以它的空间复杂度为O(1)。
冒泡排序使用了两层 for 循环，很明显时间复杂度为O(n²)
对于空间复杂度与时间复杂度这两个概念不太明白的同学可以上网搜一下如何计算，时间充裕且想系统学一下的同学可以买一本《大话数据结构》看一下，算是一本不错的算法入门书。
总结
- 特点：
（1）每次比较相邻两个元素的大小
（2）第 n 个数比较 n - 1 次 - 空间复杂度：O(1)
时间复杂度：O(n²)
OK，冒泡排序就讲到这里，如果有补充，欢迎大家评论区留言，希望你学得开心，see you soon~
网友评论