冒泡排序的基本思想:通过对 待排序序列从前向后(从下标较小的元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的数逐渐从前移向后,就像水底下的气泡一样逐渐向上冒。
优化思想:因为排序的过程中,各元素不断接近自己的位置,如果一趟比较下来发现并没有发生元素数据所在位置的交换,就说明数据已经有序了,因此要在排序过程中设置一个flag判断元素是否进行交换,从而减少不必要的比较
应用实例:将5个无序的数3,9,-1,10,-2使用冒泡排序将其排成从小到大的数列
原始数组:3,9,-1,10,-2 【相邻元素逆序则交换顺序】
第一趟比较:
3,9,-1,10,-2 【3 < 9,顺序位置不变】
3,-1,9,10,-2 【9 > -1,逆序交换位置】
3,-1,9,10,-2 【9 < 10,顺序位置不变】
3,-1,9,-2,10 【10 > -2,逆序交换位置】
下边的步骤以此类推 -->
第二趟比较(继第一趟比较的结果):
-1,3,-2,9,10 【3 > -1,逆序交换位置】
-1,-2,3,9,10 【3 > -2,逆序交换位置】
-1,-2,3,9,10 【3 < 9,顺序位置不变】
第三趟比较(继第二趟比较结果):
-2,-1,3,9,10 【-1 > -2,逆序交换位置】
-2,-1,3,9,10 【-1 < -3,顺序位置不变】
第四趟比较(继第三趟比较结果):
-2,-1,3,9,10
冒泡排序规律小结:
- 设元素个数为i,则共进行了(i-1)趟的比较,原因:确定了(i-1)个元素的位置,则最后一个元素的位置就也确定了
- 由于每一趟的比较都会确定最大数据的位置,所以下一趟中需要排序的数的个数会逐渐减少,得出规律为:第 j 趟比较中待排序的数据需要比较的次数为:i - j
- 如果我们发现在某次排序中并没有发生元素数据的交换,说明当前数据的已经排好序了,直接结束冒泡排序
代码一:冒泡排序演变过程
1 import java.util.Arrays; 2 3 //冒泡排序 4 public class BubbleSort { 5 6 public static void main(String[] args) { 7 int[] arr = {3,9,-1,10,-2 }; 8 9 //第一趟排序,将最大的数放置在数组的最后 10 int tmp = 0; //临时变量用于交换 11 for(int i = 0; i < arr.length - 1; i++) { //第一趟排序需要比较的次数 12 if (arr[i] > arr[i+1]) { 13 //逆序交换两个数 14 tmp = arr[i]; 15 arr[i] = arr[i+1]; 16 arr[i+1] = tmp; 17 } 18 } 19 System.out.println("第一趟排序后:" + Arrays.toString(arr)); 20 21 // 第二趟排序,将第二大的数放置在数组的倒数第二个位置 22 for (int i = 0; i < arr.length - 2; i++) { // 第二趟排序需要比较的次数 23 if (arr[i] > arr[i + 1]) { 24 // 逆序交换两个数 25 tmp = arr[i]; 26 arr[i] = arr[i + 1]; 27 arr[i + 1] = tmp; 28 } 29 } 30 System.out.println("第二趟排序后:" + Arrays.toString(arr)); 31 32 // 第三趟排序,将第三大的数放置在数组的倒数第三个位置 33 for (int i = 0; i < arr.length - 3; i++) { // 第三趟排序需要比较的次数 34 if (arr[i] > arr[i + 1]) { 35 // 逆序交换两个数 36 tmp = arr[i]; 37 arr[i] = arr[i + 1]; 38 arr[i + 1] = tmp; 39 } 40 } 41 System.out.println("第三趟排序后:" + Arrays.toString(arr)); 42 43 // 第四趟排序,将最大的数放置在数组的倒数第四个位置 44 for (int i = 0; i < arr.length - 4; i++) { // 第四趟排序需要比较的次数 45 if (arr[i] > arr[i + 1]) { 46 // 逆序交换两个数 47 tmp = arr[i]; 48 arr[i] = arr[i + 1]; 49 arr[i + 1] = tmp; 50 } 51 } 52 System.out.println("第四趟排序后:" + Arrays.toString(arr)); 53 } 54 55 }
总结出规律后可得以下代码:
1 import java.util.Arrays; 2 3 //冒泡排序 4 public class BubbleSort { 5 6 public static void main(String[] args) { 7 int[] arr = {3,9,-1,10,-2 }; 8 boolean flag = false; 9 int tmp = 0; 10 for(int i = 0; i < arr.length - 1; i++) { //比较的趟数 11 for(int j = 0; j <arr.length - 1 - i; j++) { //每一趟比较的次数为:总的数据个数 - 趟数 12 if (arr[j] > arr[j+1]) { 13 flag = true; 14 tmp = arr[j]; 15 arr[j] = arr[j+1]; 16 arr[j+1] = tmp; 17 } 18 } 19 if (!flag) { 20 //说明本次比较没有发生数据的交换 21 break; 22 }else { 23 //说明本轮比较发生了数据的交换,需要重置flag 24 //原因:假如共有5趟比较,在第二趟时已经发现数据并未交换【即已经时有序的了】,flag将无法变为false,也就无法提前跳出循环 25 //会继续将这5次循环运行完才结束,失去了优化的意义 26 System.out.println("第" + (i+1) + "趟比较:" + Arrays.toString(arr)); 27 flag = false; 28 } 29 } 30 System.out.println(Arrays.toString(arr)); 31 } 32 33 }
更换数据数据:
结果: