【算法系列】冒泡排序

众所周知，我们所开发的程序是 算法与数据结构 的结合，由此可见想要开发出一个优秀的程序需要两个关键因素：

• 优秀的算法，可以降低时间与空间复杂度
• 合适合理的数据结构，可以高效地存储程序所需要的数据

由此可见算法与数据结构是必须掌握的，因此我准备专门开一个【算法系列】，用于讲解常见的算法，本篇文章就准备聊聊排序算法中最基本的 冒泡排序，废话不多说，开搞！

排序的定义

在聊冒泡排序之前，我准备聊聊何为排序。在我看来，排序就是将一个 无序的 集合，以 特定特征 对 集合元素 进行位置调整，最终结果就是一个以特定特征进行排序后的 有序集合，排序的方式有很多种，常见的如下：

• 冒泡排序
• 选择排序
• 插入排序
• 希尔排序
• 桶排序
• 归并排序
• 快速排序
• 计数排序

接下来就聊聊最简单的排序：冒泡排序

冒泡排序

顾名思义，排序的过程就像是水泡从水底冒到水平面一样。以升序为例，每一轮的遍历，都会将本轮的最大值在排序过程中不断“冒泡”至集合的最后面，重复这个过程，最终达到整个集合的升序

talk is cheap，show me code，下面为代码示例

function bubbleSort(arr) {
    let len = arr.length
    for(let i = 0;i < len;i++) {
        for(let j = 0;j < len - i - 1;j++) {
            if(arr[j] > arr[j+1]){
                [arr[j],arr[j+1]] = [arr[j+1],arr[j]]
            }
        }
        
    }
    return arr
}

通过代码示例，我们可以知道此排序算法的实现过程如下

1. 确定 外循环 的轮数，轮数为集合的长度
2. 确定 内循环 的轮数，轮数为：集合长度 - 已排序的项的个数 - 1
3. 在 内循环 的每一轮去比较 相邻项 的大小，从而确定是否需要进行交换

冒泡排序的性能相对于其它排序算法较低，算法的平均时间复杂度为 **O(n^2)**，空间复杂度为 **O(1)**，这种算法通常不建议在实际的开发中使用，但作为算法的入门倒是非常适合

结语

算法是一个程序员的内功，只有修炼好了内功，才能见招拆招，于开发中立于不败之地，因此一定要好好修炼，好啦，就写到这啦，over！