[数据结构与算法 (Kotlin 语言)] 1.冒泡排序（Bubble Sort）

算法简介

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

算法原理

冒泡排序算法的原理是: 重复地走访过要排序的元素列，一次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。

算法流程图

算法步骤如下:

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

算法详解

输入: n 个数字的数组 a[n]
输出: 排好序的数字

考虑极端场景: 序正好是反的, 那么总共需要 "冒泡" n-1 次 (因为最后一次不需要了).

• 第 1 次冒泡: round=1
  j 从0 开始直到 n-1, 依次比较 if(a[j] > a[j+1]) , then swap(a[j],a[j+1]);
  最大的数字冒泡到倒数第 1 个位置(最右面).
  
  



• 
  
• 第 2 次冒泡: round=2
  j 从0 开始直到 n-2, 依次比较 if(a[j] > a[j+1]) , then swap(a[j],a[j+1]);
  第 2 大的数字冒泡到倒数第 2 个位置.
  
  



• 
  
• 第 3 次冒泡: round=3
  j 从0 开始直到 n-3, 依次比较 if(a[j] > a[j+1]) , then swap(a[j],a[j+1]);
  第 3 大的数字冒泡到倒数第 3 个位置.

...

• 第 n-1 次冒泡:round=n-1
  i 从0 开始直到 n-(n-1) = 1, if(a[j] > a[j+1]) , then swap(a[j],a[j+1]); 其实,最后一轮冒泡就是a[0] 和 a[1] 比较了.

时间复杂度

排序算法分析的方方面面

排序算法的执行效率
1.最好、最坏、平均情况时间复杂度；
2.时间复杂度的系数、常数、低阶；
3.比较次数和交换（或移动）次数。

排序算法的内存消耗

可用空间复杂度衡量，原地排序（Sorted in place）特指空间复杂度是O(1)的排序算法。

排序算法的稳定性

如1(A),2,3,4,5,1(B)，排序后保持1(A),1(B),2,3,4,5，即1(A)仍在1(B)左边，那这个就是稳定的排序算法；反之为不稳定的排序算法。

有序度、逆序度、满有序度

有序度是数组中具有有序关系的元素对的个数。
如2,1,3,4按从小到大排序，有序元素对为(1,3)，(1,4)，(3,4)，(2,3)，(2,4)，有序度为5，同理，逆序元素对的个数为(2,1)，逆序度为1。
满有序度就是有序度+逆序度，也就是n!=n*(n-1)/2。
排序的过程就是增加有序度减少逆序度的过程，直到达到满有序度，排序完成。

冒泡排序时间复杂度分析

冒泡排序包含2个操作原子，比较和交换。每交换一次，有序度加1。不管算法怎么改进，交换次数总是确定的，即为“逆序度”。

对包含n个数据的数组进行冒泡排序，最坏情况下初始状态有序度是0，需要进行n(n-1)/2次交换。最好情况下，初始状态有序度是n(n-1)/2，无需进行交换。取中间值n(n-1)/4，表示初始有序的的平均情况。也就是平均情况下需要n(n-1)/4次交换操作，比较操作肯定要比交换操作多，而这个复杂度的上限是O(n²)，所以可粗略地认为冒泡排序平均情况下时间复杂度是O(n²)。

Kotlin 代码实现

package com.light.sword.datastructure

import com.alibaba.fastjson.JSON

/**
 * @author: Jack
 * 2020-03-01 18:06
 */

fun bubbleSort(a: Array<Int>) {
    val n = a.size

    (1..n - 1).map {
        val round = it
        for (j in 0..n - 1 - round) {
            if (a[j] > a[j + 1]) {
                val max = a[j]
                a[j] = a[j + 1]
                a[j + 1] = max
            }
        }
        println("Round $round: ${JSON.toJSONString(a)}")
    }
}

fun main() {
    val a = arrayOf(2, 4, 6, 8, 3, 7, 9, 1, 5, 0)
    println("Input array:${JSON.toJSONString(a)}")
    bubbleSort(a)
}

运行输出:

Input array:[2,4,6,8,3,7,9,1,5,0]
Round 1: [2,4,6,3,7,8,1,5,0,9]
Round 2: [2,4,3,6,7,1,5,0,8,9]
Round 3: [2,3,4,6,1,5,0,7,8,9]
Round 4: [2,3,4,1,5,0,6,7,8,9]
Round 5: [2,3,1,4,0,5,6,7,8,9]
Round 6: [2,1,3,0,4,5,6,7,8,9]
Round 7: [1,2,0,3,4,5,6,7,8,9]
Round 8: [1,0,2,3,4,5,6,7,8,9]
Round 9: [0,1,2,3,4,5,6,7,8,9]

参考资料

​​https://www.jianshu.com/p/60b966bf4d09​​​​https://baike.baidu.com/item/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F/4602306​​​​https://www.jianshu.com/p/4018cb3e1639​​

Kotlin 开发者社区

国内第一Kotlin 开发者社区公众号，主要分享、交流 Kotlin 编程语言、Spring Boot、Android、React.js/Node.js、函数式编程、编程思想等相关主题。

越是喧嚣的世界，越需要宁静的思考。