1.概叙

冒泡排序就是依次比较相邻的两个数，将值较大的数放到后面的排序算法。每进行一趟排序都会找出一个较大值，所以每进行一趟排序，就会少比较一次

排序过程

初始化:

3,  6,  8,  2,  9,  1

第一趟排序:

第一次排序：3和6比较，6大于3，交换位置： 3 6 8 2 9 1

第二次排序：6和8比较，6小于8，不交换位置：3 6 8 2 9 1

第三次排序：8和2比较，8大于2，交换位置： 3 6 2 8 9 1

第四次排序：8和9比较，8小于9，不交换位置：3 6 2 8 9 1

第五次排序：9和1比较：9大于1，交换位置： 3 6 2 8 1 9
第一趟排序之后，找到最大值

3,  6,  2,  8,  1,  9

第二趟排序:

第一次排序：3和6比较，3小于6，不交换位置：3 6 2 8 1 9

第二次排序：6和2比较，6大于2，交换位置： 3 2 6 8 1 9

第三次排序：6和8比较，6小于8，不交换位置：3 2 6 8 1 9

第四次排序：8和1比较，8大于1，交换位置： 3 2 6 1 8 9

第二趟比较之后，找到第二大的值:

3,  2,  6,  1,  8,  9

第三趟排序:

第一次排序：3和2比较，3大于2，交换位置： 2 3 6 1 8 9

第二次排序：3和6比较，3小于6，不交换位置：2 3 6 1 8 9

第三次排序：6和1比较，6大于1，交换位置： 2 3 1 6 8 9

第三趟排序之后,找到第三大的值:

2,  3,  1,  6,  8,  9

第四趟排序:

第一次排序：2和3比较，2小于3，不交换位置：2 3 1 6 8 9

第二次排序：3和1比较，3大于1，交换位置： 2 1 3 6 8 9

第四趟排序之后的结果

2,  1,  3,  6,  8,  9

第五趟排序

第一次排序：2和1比较，2大于1，交换位置： 1 2 3 6 8 9

排序之后的结果

1,  2,  3,  6,  8,  9

2.代码:

class BubbleSort {
    companion object{
        @JvmStatic
        fun main(args: Array<String>) {
            var array= intArrayOf(3,6,8,2,9,1)
             bubleSort(array)
            array.forEach {
                print(it)
            }
        }

        fun bubleSort(array:IntArray){
            // 外层循环控制排序趟数
            for (i in 0 until  array.size-1){ 
                // 内层循环控制每一趟排序多少次
                for (j in 0 until  (array.size-1-i)){
                    if(array[j]>array[j+1]){
                        var t=array[j]
                        array[j]=array[j+1]
                        array[j+1]=t
                    }
                }
            }
        }
    }
}

3.时间复杂度

根据上面这种冒泡实现，若原数组本身就是有序的（这是最好情况），仅需n-1次比较就可完成；若是倒序，比较次数为 n-1+n-2+...+1=n(n-1)/2，交换次数和比较次数等值。所以，其时间复杂度依然为O(n²）