冒泡排序和选择排序的时间空间复杂度是一样的吗?

Question

如题所述

Answer 1

冒泡排序和选择排序的时间复杂度，空间复杂度都是相同的，他们的外层循环次数，乃至总的比较次数也是相同的。不同的地方在于，大多数情况下选择排序的交换操作次数会比冒泡更少，会高那么一点运行效率，再一个冒泡排序是稳定的（前提是相等的数据不进行互换），选择排序是不稳定的。
冒泡算法的逻辑在于，让最大的数不断后移，（就像水中的气泡，越上浮越大）一次外层循环可以决定出一个最大的数。如果序列有n个数据，那么外层循环需要n-1次，每次外层循环的次数是 n-外层循环的轮数。
选择排序的逻辑在于，把最大的数，次最大的数一个一个拎出来，放在它应当存在的位置。循环次数和比较次数和冒泡一样。