目录
- 前言
- 基本概念
- 冒泡排序规则
- 使用Java实现冒泡排序
- 番外篇:冒泡排序的稳定性
- 结束语
前言
如果你是计算机专业毕业的科班出身的毕业生,或者你是做软件开发工作,肯定对Java开发并不陌生,Java语言是程序圈经久不衰的经典编程语言。其实每一种编程语言都有它的特点,而且好多经典算法在编程语言中都是可以实现的,比如经典的十大排序算法,基本在每一种编程语言中都可以运用。那么本文就来分享一下在Java开发中实现冒泡排序的使用,冒泡排序是最经典的十大排序算法之一,它是最简单、最经典的,不仅基础而且重要,下面就来详细介绍一下冒泡排序的规则、Java代码的实现,并分享一些最优解以及优化思路,帮助读者更好地理解和使用这个算法。
基本概念
根据之前的惯例,先来了解知识点的基本概念,根据自己对冒泡排序的理解,结合专业的解释来看,冒泡排序就是从序列中的第一个元素开始,依次对相邻的两个元素进行比较,如果前一个元素大于后一个元素则交换它们的位置;如果前一个元素小于或等于后一个元素,则不交换它们。这一比较和交换的操作,一直持续到最后一个还未排好序的元素为止。
虽然描述有一点点的绕,但是它的原理很简单,就是进行排序的时候,如果相邻2个元素,前面大于后面就交换位置,如果前面小于后面则不交换位置,以此类推,直到最后一个元素排序好为止。
冒泡排序规则
再来了解一下冒泡排序的规则,据个人所知,冒泡排序的基本思想其实通过相邻元素之间的比较和交换,然后将较大的元素逐渐“冒泡”到数组的末尾,直到最大的排到数组的最后一个位置为止,具体规则可以总结以下几点:
1、从数组的第一个元素开始,比较相邻的两个元素的大小。
2、如果前一个元素大于后一个元素,就交换它们的位置。
3、然后继续向后比较,直到最后一个元素为止。
4、反复重复以上步骤,而且每次循环将最大的元素“冒泡”到当前未排序的末尾。
5、最后,重复执行n-1次循环,直到所有元素都排好序为止。
使用Java实现冒泡排序
上面分享了冒泡排序的概念和规则,想必读者关于冒泡排序的理论知识都已经掌握了,那么接下来就来通过Java来实现冒泡排序这一经典的排序算法,下面就是使用Java语言实现冒泡排序的代码,如下所示:
代码语言:java复制public class BubbleSort {
public static void bubbleSort(int[] array) {
int n = array.length;
for (int i = 0; i < n - 1; i ) {
for (int j = 0; j < n - i - 1; j ) {
if (array[j] > array[j 1]) {
// 交换相邻元素位置
int temp = array[j];
array[j] = array[j 1];
array[j 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] array = {5, 2, 8, 12, 3};
bubbleSort(array);
System.out.println("输出排序结果:");
for (int i : array) {
System.out.print(i " ");
}
}
}
通过上面的代码可以知道,使用Java语言通过使用两层嵌套循环实现了冒泡排序,其中,外层循环控制进行n-1次比较和交换的轮数,内层循环用于比较相邻元素并执行交换操作,所以是两层循环使用。核心代码虽然不多,但是两层循环是核心,切记。
优化思路
任何一种算法有好的地方,也有劣势,冒泡排序也不例外。虽然冒泡排序是一种简单又直观的排序算法,但在Java实际开发中,它的效率相对较低,给程序性能也能造成影响。所以为了提高在Java中使用冒泡排序的性能,个人觉得可以从下面几个点来进行优化,具体如下所示:
1、设置标志位:如果在一次内层循环过程中没有发生元素交换,则说明该数组已经有序了,可以提前结束排序的流程过程。
2、设置边界点:实际使用中的时候,可以在每次内层循环中记录上一次交换的位置,然后作为下一轮内层循环的边界点,这样就可以避免对已经排好序的元素再进行重复的比较,多做“无用功”。
3、针对部分有序数组:在实际开发中,如果数组的后部分已经是有序的,就可以在每次内层循环的时候,记录最后一次交换的位置,然后把该位置作为下一轮内层循环的边界,这样可以节省循环遍历的次数。
上面几点是个人关于使用冒泡排序的优化想法,仅代表个人观点,如果有好的优化思路,可以在评论区留言交流。但是个人觉得以上优化思路可以有效减少冒泡排序的比较和交换次数,从而提高排序的效率,完美的解决了冒泡排序的“先天缺陷”。下面分享一上文示例关于冒泡排序的执行流程步骤,需要说明一下,图中例子较为简单,不喜勿喷,具体如下所示:
番外篇:冒泡排序的稳定性
上文也介绍了关于冒泡排序的理论知识,冒泡排序其实就是把小的元素往前调换,或者把大的元素往后移动。比较的是相邻的两个元素之间的比较,交换也是在这两个元素之间进行交换的。
那么,若两个元素相等,你应该不会无聊地再把它俩个交换一下;若两个相等的元素没有相邻,那么即使通过前面的两两交换把这两个变成相邻起来,这时候也不会进行交换,所以相同元素的前后顺序并没有发生改变,这就是为什么说冒泡排序是一种稳定排序算法的原因所在了。
这里再单独举个例子,随机生成一组数字,然后用冒泡排序执行一下,主要是为了说明冒泡排序的稳定性,具体如下:
原始待排序数组| 6 | 2 | 4 | 1 | 5 |7 |
第一趟排序(外循环)
代码语言:c复制第一次两两比较,6 > 2交换(内循环)
交换前状态| 6 | 2 | 4 | 1 | 5 | 7 |
交换后状态| 2 | 6 | 4 | 1 | 5 | 7 |
代码语言:c复制第二次两两比较,6 > 4交换
交换前状态| 2 | 6 | 4 | 1 | 5 | 7 |
交换后状态| 2 | 4 | 6 | 1 | 5 | 7 |
代码语言:c复制第三次两两比较,6 > 1交换
交换前状态| 2 | 4 | 6 | 1 | 5 | 7 |
交换后状态| 2 | 4 | 1 | 6 | 5 | 7 |
代码语言:c复制第四次两两比较,6 > 5交换
交换前状态| 2 | 4 | 1 | 6 | 5 | 7 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 7 |
代码语言:c复制第五次两两比较,6 < 7不交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 7 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 7 |
第二趟排序(外循环)
代码语言:c复制第一次两两比较,2 < 4不交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 7 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 7 |
代码语言:c复制第二次两两比较,4 > 1交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 7 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 7 |
代码语言:c复制第三次两两比较,4 < 5不交换
交换前状态| 2 | 1 | 4 | 5 | 6 | 7 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 7 |
代码语言:c复制第四次两两比较,5 < 6不交换
交换前状态| 2 | 1 | 4 | 5 | 6 | 7 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 7 |
第三趟排序(外循环)
代码语言:c复制第一次两两比较,2 > 1交换
交换后状态| 2 | 1 | 4 | 5 | 6 | 7 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 7 |
代码语言:c复制第二次两两比较,2 < 4不交换
交换后状态| 1 | 2 | 4 | 5 | 6 | 7 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 7 |
代码语言:c复制第三次两两比较,4 < 5不交换
交换后状态| 1 | 2 | 4 | 5 | 6 | 7 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 7 |
第四趟排序(外循环),无交换
第五趟排序(外循环),无交换
排序执行完毕,输出最终结果:1 2 4 5 6 7
结束语
通过本文关于使用Java来实现冒泡排序的操作,想必读者都已经掌握了吧,尤其是刚入门Java的开发者需要好好掌握,真的很有用的。大家都知道冒泡排序是最经典的十大排序算法之一,通过相邻元素的比较和交换实现元素的逐渐有序。上文通过Java代码实现了冒泡排序,并介绍了一些优化思路,帮助读者更好地理解和应用这个算法。冒泡排序虽然简单,但是在实际开发应用中,我们常常也会去使用更高效、更适合的排序算法来处理实际的大数据 情况。所以,作为开发者,去了解和掌握其他的排序算法也是很重要的,大家抓紧学习和掌握更多算法,一起加油吧!