前端算法之排序(一)---- 冒泡排序

写在前面

排序算法是《数据结构与算法》中最基本的算法之一。

作为一个前端程序员,算法或许只在面试时会有所提及,日常工作中似乎用的并不多,但我们依然要重视算法,这不仅是为了面试时胸有成竹,更何况算法本身也有自己的魅力!!

这个系列的文章的初衷是为了总结一下前端程序员应该掌握的算法,尽管前文说不仅仅为了面试,但我们功利一点来看,我们学习算法的首要目的确实是为了应对面试,因此,这一个系列的文章,笔者会尽量写得通俗易懂,毕竟只有你完全理解了,面试时才能说得出来。

因此,这个系列的文章既适用于对算法感兴趣想要入门的同学,也适用于面向面试开发的同学。希望看到文章的小伙伴们能有所收获,这就是我最大的愿望了。

对于讲解所使用的语言,我会使用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~

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 215,923评论 6 498
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,154评论 3 392
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 161,775评论 0 351
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,960评论 1 290
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,976评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,972评论 1 295
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,893评论 3 416
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,709评论 0 271
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,159评论 1 308
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,400评论 2 331
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,552评论 1 346
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,265评论 5 341
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,876评论 3 325
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,528评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,701评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,552评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,451评论 2 352

推荐阅读更多精彩内容