排序算法——冒泡排序

一、算法简介

冒泡排序（Bubble Sort）是一种计算机科学最简单的排序算法之一。

它通过重复地走访要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经完成排序。

1. 算法原理

冒泡排序算法的动作原理如下：（从后往前）

1. 比较相邻的元素。如果前面的元素比第二个大，那么就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这样每循环一次，最大的数都会移到最后面。
3. 针对所有的元素重复以上步骤，除最后一个元素外。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

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)
}