本文主要是介绍BubbleSort（冒泡排序），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
| 平均时间 复杂度 | 最差时间 复杂度 | 最佳时间 复杂度 | 空间复杂度 |
| O(n^2) | O(n^2) | O(n) | O(1) |
| 稳定 | |||
public static void bubbleSort( int[] arr ) {if( arr == null | arr.length < 2 ) {return;}for( int j = arr.length - 1; j > 0; j-- ) {findMax( arr, j );}}static void findMax( int[] arr, int n ){for(int i = 0; i < n; i++ ){if( arr[ i ] > arr[ i+1 ] ){swap( arr, i, i+1 );}}}| 轮次 | 1 | 2 | 3 | k | n-3 | n-2 | n-1 | n |
| 几个数字参与 | n | n-1 | n-2 | n-k+1 | 4 | 3 | 2 | 1 |
| 比较次数 | n-1 | n-2 | n-3 | n-k | 3 | 2 | 1 | 0 |
| 交换次数 | [0,n-1] | [0,n-2] | [0,n-3] | [0,n-k] | [0,3] | [0,2] | [0,1] | 0 |
时间复杂度证明如下：
比较次数
an = n-1
Sn = (n-1) + (n-2) + (n-3) + ... + (n-k) + ... + 3 + 2 + 1 + 0 ≈ O(n^2)
交换次数
an = [0,n-1]
Sn = [0,n-1] + [0,n-2] + [0,n-3] + … + [0,n-k] + ... + [0,3] + [0,2] + [0,1] + 0 ≈ O(n^2)
结果：
平均时间复杂度 = 最差时间复杂度 = O(n^2)
最佳时间复杂度 = O(n)
这篇关于BubbleSort（冒泡排序）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
