冒泡排序（Bubble Sort）
- 冒泡排序：是一种简单的排序算法，其基本思想是通过重复遍历要排序的列表，比较相邻的元素，并在必要时（即前面的数比后面的数大的时候）交换它们的位置，从而将较大的元素逐渐“冒泡”到列表的末尾。这个过程会重复进行（第一次把最大的元素放在列表的末尾，第二次把第二大的元素放在列表的倒数第二的位置，以此类推，只需执行(
数组的长度-1次)这个过程即可），直到整个列表被排序。 - 冒泡排序主要有两个for循环组成
- 外层for循环主要用于控制数组循环遍历的次数
- 内层for循环主要用于元素位置的交换（把较大的元素往后移动）
冒泡排序初代代码：减少比较次数
public class BubbleSort {public static void main(String[] args) {int[] arr ={24,69,80,57,13};System.out.println("排序前的数组:");printArray(arr);bubbleSort(arr);System.out.println("排序后的数组:");printArray(arr);}public static void bubbleSort(int[] arr) {int n = arr.length; for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;swapped = true; }}}}public static void printArray(int[] arr) {for (int num : arr) {System.out.print(num + " ");}System.out.println();}}
案例分析
- 以int[] arr= {24,69,80,57,13};举例
- 外层for循环第1轮：把最大的数放在最后的位置
- 前一个数和后一个数比较，如果前者大就交换位置（内层for循环）
- 第1次比较[24,69,80,57,13] 第1个和第2个比
- 第2次比较[24,69,80,57,13] 第2个和第3个比
- 第3次比较[24,69,57,80,13] 第3个和第4个比（
80比57大，所以80和57交换位置） - 第4次比较[24,69,57,13,80] 第4个和第5个比（
80比13大，所以80和13交换位置）
- 外层for循环第2轮：把第二大的数放在倒数第二个位置
- 前一个数和后一个数比较，如果前者大就交换位置（内层for循环）
- 第1次比较[24,69,57,13,80] 第1个和第2个比
- 第2次比较[24,57,69,13,80] 第2个和第3个比
- 第3次比较[24,57,13,69,80] 第3个和第4个比
- 外层for循环第3轮：把第三大的数放在倒数第三个位置
- 前一个数和后一个数比较，如果前者大就交换位置（内层for循环）
- 第1次比较[24,57,13,69,80] 第1个和第2个比
- 第2次比较[24,13,57,69,80] 第2个和第3个比
- 外层for循环第4轮：把第四大的数放在倒数第四个位置
- 前一个数和后一个数比较，如果前者大就交换位置（内层for循环）
- 第1次比较[13,24,57,69,80] 第1个和第2个比
- 总结
-
- 一共有5个元素（数组的长度为n，n=5）
-
- 一共进行了4轮排序（需要进行n-1轮排序）
-
- 每一轮排序可以确定一个数的位置，比如第一轮排序确定最大的数…
-
- 当进行比较时，如果前面的数大于后面的数，就交换
-
- 每轮的比较次数在减少4->3->2->1
冒泡排序改进代码：通过swapped变量减少冒泡次数
- 优化点：如果某一轮冒泡没有发生交换，则表示所有数据有序，可以结束外层循环
public class BubbleSort {public static void main(String[] args) {int[] arr ={24,69,80,57,13};System.out.println("排序前的数组:");printArray(arr);bubbleSort(arr);System.out.println("排序后的数组:");printArray(arr);}public static void bubbleSort(int[] arr) {int n = arr.length; boolean swapped;for (int i = 0; i < n - 1; i++) {swapped = false; for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;swapped = true; }}if (!swapped) {break;}}}public static void printArray(int[] arr) {for (int num : arr) {System.out.print(num + " ");}System.out.println();}}
冒泡排序最终实现
- 优化点：用一个死循环作为外层循环，每次通过记录最后一次交换索引位置进行判断，如果在索引为0的位置，则可以结束循环。
public class BubbleSort {public static void main(String[] args) {int[] arr ={24,69,80,57,13};System.out.println("排序前的数组:");printArray(arr);bubbleSort(arr);System.out.println("排序后的数组:");printArray(arr);}public static void bubbleSort(int[] arr) {int n = a.length - 1;while (true) {int last = 0; for (int i = 0; i < n; i++) {System.out.println("比较次数" + i);if (a[i] > a[i + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;last = i;}}n = last;System.out.println("第轮冒泡"+ Arrays.toString(a));if (n == 0) { break;}}}public static void printArray(int[] arr) {for (int num : arr) {System.out.print(num + " ");}System.out.println();}}
- 一直冒泡，每轮冒泡时，最后一次交换的索引可以作为下一轮冒泡的比较次数，如果这个值为零，表示整个数组有序，直接退出外层循环即可。
