冒泡排序/快速排序

冒泡排序和快速排序都是交换类排序

为啥子要交换呢 因为"房价"贵,另外开空间"boss"会哭穷,嘤嘤嘤。

心软的两位大哥就在自己的n平方地里面来回折腾,没办法呀这就是人生啊。

冒泡大哥觉得每次找个最大值放在数组最后面即可,让每个"小朋友"和自己后面的比一下,要是比后面的高就主动换个位置,挡着人家可不好。一共有n-1局比拼,每次比拼总有一位大哥在每一次比拼的时候一路向后,承受了太多太多,这种创伤只能承受一局,所以每局结束的比拼的位置就到上一局的前一个位置即可。

快速大哥恰恰相反的想法(os:我要把矮子找出来),为了减少邻里纷争,快速大哥想了一个招,记录当前的最矮"小盆友"的位置和数据,每次把这个数据记在心里,默默扫一遍后面的,如果碰到的更矮的就更新一下心里的数据,一轮比完了以后把心里最矮的喊到前面来(此时可能交换),同样需要n-1局比拼 。

最坏复杂度: o(n^2)

最坏交换次数: 1)冒泡:n(n-1)/2   

                        2) 选择:n

比较次数:n(n-1)/2

空间复杂度:o(n)

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

友情链接更多精彩内容