Question

冒泡排序时间复杂度

Answer 1

O（N^2）。

冒泡排序的时间复杂度为O（N^2），每次比较两个相邻元素，如果他们的顺序错误就把它们交换过来。

例如我们需要将12，35，99，18，76，5个数进行从大到小排序，既然是从大到小排序，也就是越小越靠后。首先比较第一个数和第二个数，第一个是12，第二个是35，发现12小于35，由于是越小越靠后，因此要对这两个数交换位置，那么交换后的顺序为35，12，99，18，76。

按照之前的方法，我们比较第二个和第三个数，第二个是12第三个是99，99大于12，所以要交换两个数的位置，交换过的顺序为35，99，12，18，76。以此类推即可。

特点说明

冒泡排序是一种简单、稳定的交换排序方法，属于最为基础的排序方法之一。其时间复杂度最好情况为O（n）、最差与平均情况为O（n²），空间复杂度为O（1）。

 以升序排序为例，比较两个相邻的数，当后者大于前者时，二者交换；当后者小于等于前者时，继续检索。每交换一轮都能将未排序序列中的最大值交换至未排序序列尾，成为已排序序列头。同时每一轮交换结束后下一轮比较次数-1，当比较次数为0时排序完成。