一、算法简介
冒泡排序（Bubble Sort）是一种计算机科学最简单的排序算法之一。
它通过重复地走访要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经完成排序。
1. 算法原理
冒泡排序算法的动作原理如下：（从后往前）
- 比较相邻的元素。如果前面的元素比第二个大，那么就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这样每循环一次，最大的数都会移到最后面。
- 针对所有的元素重复以上步骤，除最后一个元素外。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
2. 算法分析
2.1 时间复杂度
- 最好：初始状态为正序
当数列的初始状态为正序时，所需的关键字比较次数$C$和记录移动次数$M$均达到最小值：$C_{min}=n-1,M_{min}=0$，此时，时间复杂度为$O(n)$。
- 最坏：初始状态为逆序
当数列的初始状态是反序时，需要进行$n-1$趟排序。每趟排序要进行$n-i$次关键字的比较($1≤i≤n-1$)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
$$
C_{max}=\frac{n(n-1)}{2}=O(n^2)
$$
$$
M_{max}=\frac{3n(n-1)}{2}=O(n^2)
$$
冒泡排序的最坏时间复杂度为$O(n^2)$。
综上，因此冒泡排序的平均时间复杂度为$O(n^2)$。
2.2 空间复杂度
冒泡排序的空间复杂度取决于交换两个元素位置所采用的算法。
| 算法过程 | 优缺点 | 空间复杂度 |
|---|---|---|
| temp=a;a=b;b=a; | 消耗空间 | $O(1)$ |
| a=a+b;b=a-b;a=a-b; | 可能会造成越界 | $O(0)$ |
| a=a*b;b=a/b;a=a/b; | 可能会造成越界 | $O(0)$ |
| a=a^b;b=a^b;a=a^b; | 逻辑较复杂 | $O(0)$ |
2.3 稳定性
冒泡排序就是把小的元素向前移或把大的元素向后移，比较的是两个相邻的元素，交换也是发生在这两个元素之间。所以，如果两个元素相等，不需要进行交换；如果两个元素没有相邻，那么即使通过前面的两两交换氢两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定的排序算法。
3. 伪代码
BUBBLE-SORT(A){
swapped
for(i = A.length downto 1){
swapped = false
for(j = 1 to i ){
if(A[j+1]>A[j]){
temp = A[j]
A[j] = A[j+1]
A[j+1] = temp
break = true
}
}
if(!swapped) break
}
}
4. 算法流程
冒泡排序流程
二、算法实现
1. Kotlin
/**
* 冒泡排序
* 1. 外层循环：需要遍历的元素个数
* 2. 内层循环：比较相邻元素的大小
* @author likly
* @version 1.0
*/
/**
* 冒泡排序
* @param array 要排序的数组
* @param debug 是否输入调试信息
*/
fun bubbleSort(array: Array<Int>,debug:Boolean = false){
var swapped = false
for(i in array.size-1 downTo 1){
swapped = false
for(j in 0 until i){
if(array[j+1] < array[j]){
val temp = array[j]
array[j] = array[j+1]
array[j+1] = temp
swapped = true
}
if(debug){
printlnArray("第${array.size -i}*${j+1}次冒泡",array = array)
}
}
if(!swapped) break
}
}
fun main(args: Array<String>) {
val array = arrayOf(4,6,5,2,3,1)
printlnArray("排序前",array)
bubbleSort(array,true)
printlnArray("排序后",array)
}
