算法简介
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
算法原理
冒泡排序算法的原理是: 重复地走访过要排序的元素列，一次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。
算法流程图
算法步骤如下:
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
算法详解
输入: 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、函数式编程、编程思想等相关主题。
越是喧嚣的世界，越需要宁静的思考。
网友评论