BubbleSort
冒泡排序(Bubble Sort) 是一种简单的排序算法,它重复遍历列表,比较相邻的两个元素,如果它们的顺序错误则交换它们。
冒泡排序(Bubble Sort)
基本原理
依次比较相邻的两个元素,如果相邻的两个元素的顺序是错误的,则将它们交换,直至没有元素需要交换,排序完成。
在实现上有两种方法:
- 每一轮让未排序的最大元素交换到正确位置,以下称之为"最大冒泡"
- 每一轮让未排序的最小元素交换到正确位置,以下称之为"最小冒泡"
算法步骤
以最大冒泡为例:
- 比较相邻的元素。如果第一个比第二个大,就交换它们两个。
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数,是已排序的。
- 对剩下所有未排序的元素重复以上步骤,直至所有元素都是已排序的。
动画演示
以最小冒泡为例:
参考实现
1 | import java.util.Arrays; |
复杂度分析
排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 排序方式 | 稳定性 |
---|---|---|---|---|---|---|
冒泡排序 | \(O(n^2)\) | \(O(n)\) | \(O(n^2)\) | \(O(1)\) | In-place | 稳定 |
References
-
2019-05-24
插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
-
2019-05-24
桶排序(Bucket sort)或箱排序(Bin sort),是一个排序算法,工作的原理是将数组分到有限数量的桶里。每个桶再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是 鸽巢排序 的一种归纳结果。
-
2019-05-24
在计算机科学中,选择排序(Selection sort)是一种排序算法,切确的说是就地比较排序。它具有 \(O(n^2)\) 时间复杂度,使其在大型列表上效率低下,并且通常比类似的插入排序更差。选择排序因其简单性而着称,并且在某些情况下具有优于更复杂算法的性能优势,特别是在辅助存储器有限的情况下。
-
2019-05-24
计数排序(Counting sort)是一种稳定的线性时间排序算法。该算法于1954年由 Harold H. Seward 提出。计数排序使用一个额外的数组 C ,其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数。然后根据数组 C 来将 A 中的元素排到正确的位置。
-
2019-05-24
基数排序(Radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到 1887 年 Herman Hollerith 在打孔卡片制表机(Tabulation Machine)上的贡献。