
排序逻辑
设数组的长度为 n。
首先,对 n 个元素执行“冒泡”,将数组的最大元素交换至正确位置。
接下来,对剩余 n-1 个元素执行“冒泡”,将第二大元素交换至正确位置。
以此类推,经过 n-1 轮“冒泡”后,前 n-1 大的元素都被交换至正确位置。
仅剩的一个元素必定是最小元素,无须排序,因此数组排序完成。
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| public class BubbleSort {
private static void sort(int[] nums) { for (int i = nums.length - 1; i > 0; i--) { for (int j = 0; j < i; j++) { if (nums[j] > nums[j + 1]) { int temp = nums[j]; nums[j] = nums[j + 1]; nums[j + 1] = temp; } } } }
public static void main(String[] args) { int[] nums = {5, 3, 7, 2, 0, 3, 8}; sort(nums); for (int num : nums) { System.err.println(num); } } }
|
效率优化
我们发现,如果某轮“冒泡”中没有执行任何交换操作,说明数组已经完成排序,可直接返回结果。因此,可以增加一个标志位 flag
来监测这种情况,一旦出现就立即返回。
经过优化,冒泡排序的最差时间复杂度和平均时间复杂度仍为 O(n^2) ;但当输入数组完全有序时,可达到最佳时间复杂度 O(n) 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| private static void sortWithFlag(int[] nums) { for (int i = nums.length - 1; i > 0; i--) { boolean flag = false; for (int j = 0; j < i; j++) { if (nums[j] > nums[j + 1]) { int tmp = nums[j]; nums[j] = nums[j + 1]; nums[j + 1] = tmp; flag = true; } } if (!flag) break; } }
|
算法特性
- 时间复杂度为O(n^2) 、自适应排序:各轮“冒泡”遍历的数组长度依次为 n−1、n−2、…、2、1 ,总和为 (n−1)n/2 。在引入
flag
优化后,最佳时间复杂度可达到 O(n) 。
- 空间复杂度为 O(1)、原地排序:指针 i 和 j 使用常数大小的额外空间。
- 稳定排序:由于在“冒泡”中遇到相等元素不交换。