首页 / 算法 / 交换排序算法之冒泡排序
交换排序算法之冒泡排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了交换排序算法之冒泡排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3953字，纯文字阅读大概需要6分钟。
内容图文
八种排序算法可以按照如图分类，本文主要介绍冒泡排序。
交换排序
所谓交换，就是序列中任意两个元素进行比较，根据比较结果来交换各自在序列中的位置，以此达到排序的目的。
冒泡排序
冒泡排序是一种简单的交换排序算法，以升序排序为例，其核心思想是：
- 从第一个元素开始，比较相邻的两个元素。如果第一个比第二个大，则进行交换。
- 轮到下一组相邻元素，执行同样的比较操作，再找下一组，直到没有相邻元素可比较为止，此时最后的元素应是最大的数。
- 除了每次排序得到的最后一个元素，对剩余元素重复以上步骤，直到没有任何一对元素需要比较为止。
用 Java 实现的冒泡排序如下
/**
* 冒泡排序常规版
*
* <p>没有经过任何优化操作的版本
* @param arr 待排序的整型数组
* @return 比较次数
*/
public static int bubbleSortOpt1(int[] arr) {
if (arr == null) {
throw new NullPointerException();
} else if (arr.length == 0) {
return 0;
}
int temp;
int count = 0;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
count++;
}
}
return count;
}
算法优化
现在有个问题，假如待排序数组是 2、1、3、4、5 这样的情况，按照上述代码实现，第一次循环即可得出正确结果。但循环并不会停止，而是继续执行，直到结束为止。显然，之后的循环遍历是没有必要的。
为了解决这个问题，我们可以设置一个标志位，用来表示当前次循环是否有交换，如果没有，则说明当前数组已经完全排序。
/**
* 冒泡排序优化第一版
*
* <p>设置了一个标志位，用来表示当前次循环是否有交换，如果没有，则说明当前数组已经完全排序
* @param arr 待排序的整型数组
* @return 比较次数
*/
public static int bubbleSortOpt2(int[] arr) {
if (arr == null) {
throw new NullPointerException();
} else if (arr.length == 0) {
return 0;
}
int temp;
int count = 0;
for (int i = 0; i < arr.length - 1; i++) {
int flag = 1;
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = 0;
}
count++;
}
// 没有发生交换，排序已经完成
if (flag == 1) {
return count;
}
}
return count;
}
算法还可以再优化，比如 3、4、2、1、6、7、8 这个数组，第一次循环后，变为 3、2、1、4、6、7、8 的顺序，我们发现，1 之后的 4 、6、7、8 已经有序了，第二次循环就没必要对后面这段再遍历比较。
假设一次循环后数组第 i 个元素后所有元素已经有序，优化目标就是下次循环不再花费时间遍历已经有序的部分。关键在于如何定位 i 这个分界点，其实并不难，可以想象，由于 i 之前的元素是无序的，所以一定有交换发生，而 i 之后的元素已经有序，不会发生交换，最后发生交换的地点，就是我们要找的分界点。
/**
* 冒泡排序优化第二版
*
* <p>定位最后发生交换的分界点，之后的元素无需遍历。
* @param arr 待排序的整型数组
* @return 比较次数
*/
public static int bubbleSortOpt3(int[] arr) {
if (arr == null) {
throw new RuntimeException();
} else if (arr.length == 0) {
return 0;
}
int temp;
int count = 0;
int len = arr.length - 1;
for (int i = 0; i < arr.length - 1; i++) {
// 记录最后一次交换位置
int lastChange = 1;
for (int j = 0; j < len; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
// 每交换一次更新一次
lastChange = j;
}
count++;
}
len = lastChange;
}
return count;
}
整合第一版和第二版，得到最终版本的冒泡算法
/**
* 冒泡排序优化最终版
*
* <p>整合第一版和第二版
* @param arr 待排序的整型数组
* @return 比较次数
*/
public static int bubbleSortOpt4(int[] arr) {
if (arr == null) {
throw new RuntimeException();
} else if (arr.length == 0) {
return 0;
}
int temp;
int count = 0;
int len = arr.length - 1;
for (int i = 0; i < arr.length - 1; i++) {
// 记录最后一次交换位置
int lastChange = 1;
int flag = 1;
for (int j = 0; j < len; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
// 每交换一次更新一次
lastChange = j;
flag = 0;
}
count++;
}
// 没有发生交换，排序已经完成
if (flag == 1) {
return count;
}
len = lastChange;
}
return count;
}
各位可以自行设计测试数据，看看返回的比较次数大小是否减少。
性能分析
分析最优版本算法，最好的情况是一开始已经排好序，那就没必要交换了，直接返回，此时只走了外层的第一次循环，最优时间复杂度为 O(n)。
最坏的情况当然是数组是逆序的，这样里外两层循环都走了遍，最坏时间复杂度为 O( n^2 )。
空间复杂度则是用于交换的临时变量，至于标志位和其他的因算法的不同实现有差异。
内容总结
以上是互联网集市为您收集整理的交换排序算法之冒泡排序全部内容，希望文章能够帮你解决交换排序算法之冒泡排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。