前端面试不会直接挂掉的题目--冒泡排序-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

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

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

什么是冒泡排序?

冒泡排序指的是一种排序的思想,假如我们拿到一个数组,数组中是一堆无序的数字,冒泡排序就可以让这堆无序的数字变得有序,之所以叫做冒泡排序而不是其他的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的前面,这样的排序算法我们称之为稳定的排序算法,反之称为不稳定的排序算法,因此冒泡排序是稳定的。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章