前端面试不会直接挂掉的题目--冒泡排序

在准备面试的过程中，我们往往容易陷入到很多难度比较高的题目中不能自拔，却忽略了比较基础的题目，面试官在不了解我们的情况下，刚开始可能会问我们一道比较基础的算法题，比如数据结构，请问你能手写下冒泡排序吗？如果此时不会的话，可能直接结束面试了。哈哈~，让我们今天来一起学习下这个比较简单的排序算法吧~

什么是冒泡排序？

冒泡排序指的是一种排序的思想，假如我们拿到一个数组，数组中是一堆无序的数字，冒泡排序就可以让这堆无序的数字变得有序，之所以叫做冒泡排序而不是其他的XX排序，是因为冒泡排序的每一轮排序中都将最大的值置为了最后的位置上，就像冒泡一样，所以取名为冒泡排序。

冒泡排序的思想

1. 排序的轮数是数组的长度-1.
2. 每一轮排序都将最大的值放在最末尾。
3. 下一轮排序需要比较的次数都要比上一轮少一次。

实现冒泡排序

function mySort(arr) {
    let temp;
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    console.log(arr);
    return arr;
}
mySort([8,9,7,3,2,6])
复制代码

时间复杂度和空间复杂度分析

• 空间复杂度

在空间上，我们只定义了一个临时变量进行交换使用，所以空间复杂度为O(1)。

• 时间复杂度

我们分析最差情况下的时间复杂度，假如数组是完全逆序排列的，时间复杂度为：3n(n-1)/2，所以平均时间复杂度为O(n^2).

冒泡排序的稳定性

在辨别冒泡排序是否是稳定排序之前，我们首先要知道什么样的算法算是一种稳定的算法。稳定的算法通俗的讲就是假如两个值是一样的，排序前A在B的前面，排序后A还在B的前面，这样的排序算法我们称之为稳定的排序算法，反之称为不稳定的排序算法，因此冒泡排序是稳定的。