图解冒泡排序
1. 图示过程
冒泡排序图示
2. 文字叙述过程
对于一组包含n个数据的记录，冒泡排序在最坏的情况下需要进行n-1趟排序
- 第1趟：依次比较0和1、1和2、2和3...（n-2）和（n-1）索引的元素，如果发现第1个数据大于第2个数据，交换他们，经过第1趟排序，最大的元素排到了最后
- 第2趟：依次比较0和1、1和2、2和3...（n-3）和（n-3）索引的元素，如果发现第1个数据大于第2个数据，交换他们，经过第2趟排序，第二大的元素排到了倒数第二个位置
- ...
- 第n-1趟：比较0和1索引的元素，如果发现第1个数据大于第2个数据，交换他们，经过第n-1趟排序，第二小的元素排到了第二个位置
3. Java代码实现
public static void bubbleSort(int[] nums) {
int temp;
for(int i = 1; i < nums.length; i++) {
for(int j = 0; j < nums.length - i; j++) {
if(nums[j] > nums[j+1]) {
temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
}4. 复杂度
- 时间复杂度：O(n²)
- 空间复杂度：O(1)，只需要一个附加程序单元用于交换
- 稳定性：不稳定 冒泡排序是不稳定的排序算法，最好情况下（初始数组本来就有序），算法执行一趟冒泡即可，做 n-1 次比较，0次交换即可，最坏情况下（初始数组完全逆序），算法需要执行 n-1 趟冒泡，比较总次数为 n * (n-1) / 2，交换总次数为 n * (n-1) / 2
5. 优化
在上面实现的代码中，即使n个数本来就是有序的，也会进行(n-1)次排序（只比较，不交换） 优化：当数组已经有序后，就中断循环
public static void bubbleSort(int[] nums) {
int temp;
for(int i = 1; i < nums.length; i++) {
boolean flag = true;
for(int j = 0; j < nums.length - i; j++) {
if(nums[j] > nums[j+1]) {
temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
flag = false;
}
}
if(flag) {
// 如果某趟没有交换，说明数组已经有序
break;
}
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.09.12 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录