八大排序之冒泡排序（java实现）

冒泡排序：

基本介绍：

冒泡排序的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始），一次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后面，就像水里的气泡一样逐渐向上冒。
blue~
bule~ blue~
blue~
鱼吐泡泡

因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行多交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。

冒泡分析：

定义一个原始数组：2,8，-1,10,21
第一趟排序：

（1）2,8,-1,10,21
（2）2,-1,8,10,21
（3）2,-1,8,10,21
（4）2,-1,8,10,21
第二趟排序：
（1）-1,2,8,10,21
（2）-1,2,8,10,21
（3）-1,2,8,10,21
第三趟排序：
（1）-1,2,8,10,21
（2）-1,2,8,10,21
第四趟排序：
（1）-1,2,8,10,21

冒泡排序总结：

（1）一共进行数组的大小-1次的循环
（2）每一趟排序的次数在逐渐的减少，如果没有进行变化，就提前结束。

package DataStructures.sort;import java.util.Arrays;public class BubbleSort {public static void main(String[] args) {//给出一个数组{3,8,-2,9,-3}int arr[] = {3, 8, -2, 9, -3};//把冒泡排序的演变过程展示一下/** 第一趟，将最大的数排在最后* *//* //冒泡排序的时间复杂度O(n^2)int temp = 0;//临时变量，比较用for (int j = 0; j < arr.length - 1; j++) {//如果前面的数比后面的数字大，进行交换if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}System.out.printf("第%d趟排序后的数组:\n", i + 1);System.out.println(Arrays.toString(arr));* 第二趟，将arr.length-2大的数排在最后*//*for (int j = 0; j < arr.length - 2; j++) {//如果前面的数比后面的数字大，进行交换if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}System.out.println("第二趟排序后的数组:");System.out.println(Arrays.toString(arr));*//** 第三趟，将arr.length-3大的数排在最后* *//*for (int j = 0; j < arr.length - 3; j++) {//如果前面的数比后面的数字大，进行交换if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}System.out.println("第三趟排序后的数组:");System.out.println(Arrays.toString(arr));*//** 第四趟，将arr.length-4大的数排在最后* *//*for (int j = 0; j < arr.length - 4; j++) {//如果前面的数比后面的数字大，进行交换if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}System.out.println("第四趟排序后的数组:");System.out.println(Arrays.toString(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.printf("第%d趟排序后的数组:\n", i + 1);System.out.println(Arrays.toString(arr));if (!flag) {//在一趟排序中，一次交换都没有发生过break;} else {flag = false;//重置flag，进行下次判断}
}

优化后的代码：

package DataStructures.sort;import java.util.Arrays;public class BubbleSort {public static void main(String[] args) {//给出一个数组{3,8,-2,9,-3}int arr[] = {3, 8, -2, 9, -3};//把冒泡排序的演变过程展示一下/** 第一趟，将最大的数排在最后* */System.out.println("排序前");System.out.println(Arrays.toString(arr));
//测试冒泡排序bubbleSort(arr);System.out.println("排序后");System.out.println(Arrays.toString(arr));/* //冒泡排序的时间复杂度O(n^2)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.printf("第%d趟排序后的数组:\n", i + 1);System.out.println(Arrays.toString(arr));if (!flag) {//在一趟排序中，一次交换都没有发生过break;} else {flag = false;//重置flag，进行下次判断}}*//** 第二趟，将arr.length-2大的数排在最后*//*for (int j = 0; j < arr.length - 2; j++) {//如果前面的数比后面的数字大，进行交换if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}System.out.println("第二趟排序后的数组:");System.out.println(Arrays.toString(arr));*//** 第三趟，将arr.length-3大的数排在最后* *//*for (int j = 0; j < arr.length - 3; j++) {//如果前面的数比后面的数字大，进行交换if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}System.out.println("第三趟排序后的数组:");System.out.println(Arrays.toString(arr));*//** 第四趟，将arr.length-4大的数排在最后* *//*for (int j = 0; j < arr.length - 4; j++) {//如果前面的数比后面的数字大，进行交换if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}System.out.println("第四趟排序后的数组:");System.out.println(Arrays.toString(arr));*/}//将前面的冒泡排序算法，封装成 一个方法public static void bubbleSort(int arr[]) {//冒泡排序的时间复杂度O(n^2)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.printf("第%d趟排序后的数组:\n", i + 1);
//            System.out.println(Arrays.toString(arr));if (!flag) {//在一趟排序中，一次交换都没有发生过break;} else {flag = false;//重置flag，进行下次判断}}}
}

测试八万数据的时间消耗：

package DataStructures.sort;import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;public class BubbleSort {public static void main(String[] args) {//给出一个数组{3,8,-2,9,-3}//int arr[] = {3, 8, -2, 9, -3};//把冒泡排序的演变过程展示一下/** 第一趟，将最大的数排在最后* */int[] arr = new int[80000];for (int i = 0; i < 80000; i++) {arr[i] = (int) (Math.random() * 8000000);//生成80000个随机数【0,80000000】}Date data1 = new Date();SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");String data1Str = simpleDateFormat.format(data1);System.out.println("排序前的时间：" + data1Str);bubbleSort(arr);Date data2 = new Date();//new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");String data2Str = simpleDateFormat.format(data2);System.out.println("排序后的时间：" + data2Str);
//        System.out.println("排序前");
//        System.out.println(Arrays.toString(arr));
//测试冒泡排序
//        bubbleSort(arr);
//        System.out.println("排序后");
//        System.out.println(Arrays.toString(arr));/* //冒泡排序的时间复杂度O(n^2)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.printf("第%d趟排序后的数组:\n", i + 1);System.out.println(Arrays.toString(arr));if (!flag) {//在一趟排序中，一次交换都没有发生过break;} else {flag = false;//重置flag，进行下次判断}}*//** 第二趟，将arr.length-2大的数排在最后*//*for (int j = 0; j < arr.length - 2; j++) {//如果前面的数比后面的数字大，进行交换if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}System.out.println("第二趟排序后的数组:");System.out.println(Arrays.toString(arr));*//** 第三趟，将arr.length-3大的数排在最后* *//*for (int j = 0; j < arr.length - 3; j++) {//如果前面的数比后面的数字大，进行交换if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}System.out.println("第三趟排序后的数组:");System.out.println(Arrays.toString(arr));*//** 第四趟，将arr.length-4大的数排在最后* *//*for (int j = 0; j < arr.length - 4; j++) {//如果前面的数比后面的数字大，进行交换if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}System.out.println("第四趟排序后的数组:");System.out.println(Arrays.toString(arr));*/}//将前面的冒泡排序算法，封装成 一个方法public static void bubbleSort(int arr[]) {//冒泡排序的时间复杂度O(n^2)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.printf("第%d趟排序后的数组:\n", i + 1);
//            System.out.println(Arrays.toString(arr));if (!flag) {//在一趟排序中，一次交换都没有发生过break;} else {flag = false;//重置flag，进行下次判断}}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！