冒泡排序的时间复杂度

一般情况下冒泡排序的时间复杂度为O(n^2)

改进后的冒泡排序的，在已经有序 情况下时间复杂度为O(n)，最坏情况下的时间复杂度为O(n^2)，平均时间复杂度为O(n^2)

冒泡排序时间复杂度怎么求？

冒泡排序是一种用时间换空间的排序方法，最坏情况是把顺序的排列变成逆序，或者把逆序的数列变成顺序。在这种情况下，每一次比较都需要进行交换运算。

举个例子来说，一个数列 5 4 3 2 1 进行冒泡升序排列，***次大循环从***个数（5）开始到倒数第二个数（2）结束，比较过程：先比较5和4，4比5小，交换位置变成4 5 3 2 1；比较5和3，3比5小，交换位置变成4 3 5 2 1……最后比较5和1，1比5小，交换位置变成4 3 2 1 5。这时候共进行了4次比较交换运算，最后1个数变成了数列***数。

第二次大循环从***个数（4）开始到倒数第三个数（2）结束。进行3次比较交换运算。

……

所以总的比较次数为 4 + 3 + 2 + 1 = 10次

对于n位的数列则有比较次数为 (n-1) + (n-2) + ... + 1 = n * (n - 1) / 2，这就得到了***的比较次数。

而O(N^2)表示的是复杂度的数量级。举个例子来说，如果n = 10000，那么 n(n-1)/2 = (n^2 - n) / 2 = (100000000 - 10000) / 2，相对10^8来说，10000小的可以忽略不计了，所以总计算次数约为0.5 * N^2。用O(N^2)就表示了其数量级（忽略前面系数0.5）。

算法原理：

1.比较相邻的元素。如果***个比第二个大，就交换他们两个。

2.对每一对相邻元素作同样的工作，从开始***对到结尾的最后一对。在这一点，最后的元素应该会是***的数。

3.针对所有的元素重复以上的步骤，除了最后一个。

4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

冒泡排序时间复杂度

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时排序完成。

关于冒泡排序时间复杂度和冒泡排序时间复杂度和空间复杂度的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。