面试官：手写一个冒泡排序，并对其改进( 四 )
上面的这个虽然很好 ， 必过还是有一定的局限性 ， 比如说数组的数据量很大有10000个 ， 前面3000个杂乱无章 ， 后面7000个都是排好的 ， 而且还都比前3000个要大 ， 这时候只需要比较前3000个即可 。 但是上面的改进算法 ， 在对前3000个进行排序的时候 ， 每次还都要和后7000个比较 。 这就显得臃肿了 。 于是我们进行改进 。
这个改进就是把flag变为具体的位置了 ， 这样我们就可以记录末尾的边界 。 这个边界是排序与不排序的边界 。
三、总结
冒泡排序在笔试或者是面试的时候 ， 涉及到的时间复杂度和空间复杂度都是第一种普通情况 。 因此它的时间复杂度是O(n^2) 。 虽然简单 ， 但是时间上确实是比较长 。
我们一定要注意和选择排序的区别 ， 选择排序是走一趟找出来一个最小的值和第一个同学交换位置 。 而冒泡排序是相邻同学比较高低 ， 这样走一趟 ， 最高个就沉到末尾了 。
推荐阅读
- 雷神|原神：曾经有一个强力五星角色，却因各种“流言蜚语”，擦肩而过
- 次世代|韩国战队全军覆没，斗鱼选手实力强大，一人击溃一个队
- 手机游戏|LOL手游第一个世界赛，破晓杯火热开战，DKG能紧随EDG夺冠吗？
- xyg|月光败给XYG不敢去采访，怕主持人问他一个问题！根本没办法解释
- 卡牌|王者峡谷最难抓的五个英雄，暗信算一个，榜首玩起来非常快乐
- 传奇世界|传奇世界：盘点当年出现过哪些漏洞，有一个至今都存在？
- 扁鹊|裴擒虎虎年限定有变，嫦娥拒霜思配音引热议，扁鹊有一个好消息
- 绝地求生|不播绝地求生，跑去玩双马尾少女？PDD后又一个主播“沉迷”幻塔
- 光·遇|光遇：追光季复刻盘点，下一个返场先祖，可能是笛子或者灯泡斗篷
- 地下城与勇士|DNF：“全民云上”时代到来，一个过气小副本，究竟有何魅力？