【经典算法】冒泡排序
冒泡排序是Java中非常经典的一种排序方法,可以将多个数字进行升序排序,效率比较高。
一、冒泡排序的基本思想
冒泡排序(Bubble Sorting)的基本思想是: 通过对待排序序列从前向后(从下标较小的元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前移向后部,就象水底下的气泡一样逐渐向上冒。
冒泡排序算法的运作如下:
1、比较两个相邻的数,如果前面的数大于后面的数,则将这两个数交换位置。第一次遍历后,最大的数会被放到数组的最后位置,即array[length - 1]。
2、第二次遍历时跳过最后一个元素,因为该元素通过第一次遍历已经确定是最大值。
3、持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
二、冒泡排序的原理(图解)
冒泡排序的原理是:外层循环遍历整个数组,内层循环对相邻元素进行比较,把最大值选出来交给外层下标,依次进行。
定义的数组int arr[] = {15, 63, 97, 12, 235, 66}
第一次循环:
1、首先比较arr[0]和arr[1],即15和63;因为15< 63,因此两个数的位置不变。
[15, 63, 97, 12, 235, 66]
比较和交换对应的代码如下:
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
2、接着比较arr[1]和arr[2],即63和97;因为63 < 97,因此两个数的位置不变,如下
[15, 63, 97, 12, 235, 66]
3、接着比较arr[2]和arr[3],即97和12;因为97 > 12,因此交换两个数的位置,交换完的数组如下:
[15, 63, 12, 97, 235, 66]
4、接着比较arr[3]和arr[4],即97和235;因为97 < 235,因此两个数的位置不变,如下:
[15, 63, 12, 97, 235, 66]
5、最后比较arr[4]和arr[5],即235和66;因为235 > 66,因此交换两个数的位置,交换完的数组如下:
[15, 63, 12, 97, 66, 235]
至此第一次循环结束,由于是相邻两数比较,可以看到第一次循环我们只需要进行5次比较,即:(arr.length - 1) 次。
接着下一轮,不断循环
用具体的例子展示,每次循环需要比较的次数如下:
第一次循环:arr.length - 1 - 0
第二次循环:arr.length - 1 - 1
第三次循环:arr.length - 1 - 2
...
三、时间复杂度
在通常情况下。冒泡排序的比较次数 = (n - 1) + (n - 2) + ... + 2 + 1,即:n * (n - 1) / 2,所以冒泡排序的时间复杂度为:O(n^2)。
四、使用场景
由于冒泡排序的时间复杂度为:O(n^2)。因此,在进行量比较大的排序时,最好不要采用冒泡排序。经过简单的测试,在1000个数字以内的排序,用冒泡排序是可以接受的。1000个随机数使用冒泡排序耗时一般在5毫秒以内,但是当数字个数达到10000个时,耗时会达到100+毫秒,简直是灾难。
五、最优情况
对排序算法熟悉的人应该知道,冒泡排序最优情况的时间复杂度是:O(n),怎么得出来的了?通过上文的代码是无法达到O(n)的,需要对上文的代码进行一点点的优化,优化后的代码如下。
public static void bubbleSort(int[] arr) {
// 临时变量
int temp = 0;
// 标识变量,表示是否进行过交换
boolean flag = false;
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]) {
flag = true;
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.println("第" + (i + 1) + "趟排序后的数组");
System.out.println(Arrays.toString(arr));
// 在一趟排序中,一次交换都没有发生过
if (!flag) {
break;
} else {
// 重置flag, 进行下次判断
flag = false;
}
}
}
六、完整代码
package com.example.demo;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
/**
* @author Biyu
* @projectName demo
* @className: BubbleSort
* @description //TODO
* @date: 2023-01-10 22:44
*/
public class BubbleSort {
public static void main(String[] args) {
int arr[] = {15, 63, 97, 12, 235, 66};
Date beginDate = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String beginDateStr = simpleDateFormat.format(beginDate);
System.out.println("排序前的时间是=" + beginDateStr);
bubbleSort(arr);
Date endDate = new Date();
String endDateStr = simpleDateFormat.format(endDate);
System.out.println("排序后的时间是=" + endDateStr);
}
/**
* 冒泡排序
*
* @param arr
*/
public static void bubbleSort(int[] arr) {
// 临时变量
int temp = 0;
// 标识变量,表示是否进行过交换
boolean flag = false;
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]) {
flag = true;
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.println("第" + (i + 1) + "趟排序后的数组");
System.out.println(Arrays.toString(arr));
// 在一趟排序中,一次交换都没有发生过
if (!flag) {
break;
} else {
// 重置flag, 进行下次判断
flag = false;
}
}
}
}
运行结果:
更多推荐
所有评论(0)