文章目录
- 1、概述
- 2、传统代码
- 3、优化后代码
- 4、测试案例
1、概述
冒泡排序(Bubble Sort),是一种的较简单且常见的的排序算法。
它重复地访问排序的元素列,依次比较两个相邻的元素,如果顺序不符合要求就把他们进行交换。访问元素的工作是重复地进行,当没有相邻元素需要交换时,说明该元素列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。
2、传统代码
核心思想:我们每一次的排序只是为了得到一个最大值,并且放到末尾。然后再将剩下的数据进行排序,注意此时末尾的已经确定的值不需要再进行比较排序。即比较次数为:( n-1 ) + ( n-2 ) + ( n-3 ) + …
从小到达的排序测试代码:
public class BubbleSortTest01 {
public static void main(String[] args) {
int[] arr = {1,1, 2, 2, 25, 23, 5};
int tem;
//1.进行数组长度-1次排序(最后只剩一个数字时就不需要排序)
for (int i = 0; i < arr.length - 1; i++) {
//2.每排一次序,最大的一个数字就会被确定,所以比较的次数依次减少
for (int j = 0; j < arr.length - 1 - i; j++) {
//3.拿前一个数字直接和下一个数字进行比较,然后确定是否需要互换数值
if (arr[j] > arr[j + 1]) {
tem = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = tem;
}
}
System.out.println("第"+i+"次排序:");
System.out.println(Arrays.toString(arr));
}
}
}
3、优化后代码
传统的比较方法容易有一个弊端,假设我们传入的数组本身就是一个有序的数组,但是有序数组依然会执行相应的比较逻辑。我们可以利用标志位来解决这个问题
public class BubbleSortTest02 {
public static void main(String[] args) {
int[] arr = {1, 1, 2, 2, 25, 23, -5};
int tem;
//1.设置一个标志位,用于判断本次遍历过程,是否进行了交换顺序
boolean flag;
for (int i = 0; i < arr.length - 1; i++) {
flag = false;
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
//2.如果进行了排序,就修改对应的标志位
flag = true;
tem = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = tem;
}
}
//3.如果一次循环种没有进行交换,那就直接返回
if (flag == false) {
System.out.println("结束");
return;
}
}
System.out.println(Arrays.toString(arr));
}
}
4、测试案例
利用我们以有的条件,进行一个小案例的测试:计算将数组长度为80000的乱序数组排序所花费的时间
package pers.mobian.maopao;
import java.util.Arrays;
public class BubbleSortTest03 {
public static void main(String[] args) {
//1.创建一个大小为80000的随机数数组
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++) {
arr[i] = (int) (Math.random() * 80000);
}
long start = System.currentTimeMillis();
//2.将数组进行冒泡排序
bubbleSort(arr);
long end = System.currentTimeMillis();
//3.打印花费的时间
System.out.println("冒泡排序花费的时间为:" + (end - start));
}
//将冒泡排序封装成一个方法
public static void bubbleSort(int[] arr) {
int tem;
boolean flag;
for (int i = 0; i < arr.length - 1; i++) {
flag = false;
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
flag = true;
tem = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = tem;
}
}
if (flag == false) {
return;
}
}
}
}