冒泡排序是排序算法中最易理解的一种排序方法。 今天就让我们以非常容易理解的视频+图文+动画的形式来学习 我们的入门排序算法:冒泡排序
从前到后(即从下标较小的元素开始)依次比较相邻元素的值,若发现逆序则交换位置,使值较大的元素逐渐从前移向后部。 eg:
待排序的数:7,3,22,15,8
根据冒泡排序的思想:
第一轮排序后的结果:【22的位置被固定】3,7, 15, 8,22
第二轮排序后的结果:【15的位置被固定】3, 7, 8, 15, 22
第三轮排序后的结果:【8的位置被固定】:3, 7, 8,15, 22
第四轮排序后的结果:【7的位置被固定】:3, 7, 8,15, 22
排序到此结束
以上面的5个数为例,我们看到5个数进行排序需要进行4轮大的排序
那么n个数排序时,需要进行 (n-1) 轮大的排序。
(1)上面五个数的第 一轮排序需进行4次(5个数参与排序,数组下标0-4)
(2)上面五个数的第二轮排序需进行3次(4个数参与排序,数组下标0-3)
(3)上面五个数的第三轮排序需进行2次(3个数参与排序,数组下标0-2)
(4)上面五个数的第四轮排序需进行 1次(2个数参与排序,数组下标0-1)
package Sort; import java.util.Arrays; public class BubbleSort { // 原始数组:7,3,22,15,8数组长度为5 public static void bubbleSort(int arr[]) {// 用此方法给数组进行排序 int i = 0, temp = 0;// temp变量用来保存arr[i]和arr[i+1]中的大数 // 第一趟排序 for (i = 0; i < arr.length-1-0; i++) {//i<5 下标是0-4 //(需arr.length-1-0。因为如果只是arr.length那么当i=4时,arr[i+1]=5,不满足i<5的条件,数组会越界) if (arr[i] > arr[i + 1]) {// 如果两个数是逆序的,就交换位置 temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } System.out.println("第一次排序"+Arrays.toString(arr)); } // 第二趟排序 for (i = 0; i < arr.length-1-1; i++) {//i<4 下标是0-3, 22的位置已经确定 //(需arr.length-1-1。因为如果只是arr.length-1那么当i=3时,arr[i+1]=4,不满足i<4的条件数组会越界) if (arr[i] > arr[i + 1]) {// 如果两个数是逆序的,就交换位置 temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } System.out.println("第二次排序"+Arrays.toString(arr)); } // 第三趟排序 for (i = 0; i < arr.length-1-1-1; i++) {//i<3 下标是0-2 22、15的位置已经确定 //(需arr.length-1-1-1。因为如果只是arr.length-1-1那么当i=2时,arr[i+1]=3,不满足i<3的条件数组会越界) if (arr[i] > arr[i + 1]) {// 如果两个数是逆序的,就交换位置 temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } System.out.println("第三次排序"+Arrays.toString(arr)); } // 第四趟排序 for (i = 0; i < arr.length-1-1-1-1; i++) {//i<2 下标是0-1 22、15、8的位置已经确定 //(需arr.length-1-1-1-1。因为如果只是arr.length-1-1-1那么当i=1时,arr[i+1]=2,不满足i<2的条件数组会越界) if (arr[i] > arr[i + 1]) {// 如果两个数是逆序的,就交换位置 temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } System.out.println("第四次排序"+Arrays.toString(arr)); } } public static void main(String[] args) { int arr[] = { 7, 3, 22, 15, 8 }; bubbleSort(arr); } } 复制代码
第一轮排序:i<arr.length-1-0
第二轮排序:i<arr.length-1-1
第三轮排序:i<arr.length-1-1-1
第四轮排序:i<arr.length-1-1-1-1
所以可以用一个for循环嵌套在我们刚刚的for循环上
这个变量j的范围是0-3即j < arr.length - 1
arr.length=5,j<arr.length,j的范围[0-4]
j<arr.length-1,j的范围[0-3]
package Sort; import java.util.Arrays; public class BubbleSort { // 原始数组:7,3,22,15,8数组长度为5 public static void bubbleSort(int arr[]) {// 用此方法给数组进行排序 int i = 0, temp = 0;// temp变量用来保存大数 int j = 0; for (j = 0; j < arr.length - 1; j++) { for (i = 0; i < arr.length - 1 - j; i++) {// i<5 下标是0-4 if (arr[i] > arr[i + 1]) {// 如果两个数是逆序的,就交换位置 temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } System.out.println("第" + (j + 1) + "次排序" + Arrays.toString(arr)); } } public static void main(String[] args) { int arr[] = { 7, 3, 22, 15, 8 }; bubbleSort(arr); } } 复制代码
当第二轮排序完成后,数组已经是有序的。
但是没有一个标志去告诉for循环,数组已经有序,该退出for循环了。
所以针对这个问题,我们定义一个boolean flag = false;
来判断是否结束for循环
如果flag == false,说明数组已经有序,可以退出for循环了
如果flag == true,我们需要让flag=false;
以便下次数组有序时,可以退出for循环。
package Sort; import java.util.Arrays; public class BubbleSort { // 原始数组:7,3,22,15,8数组长度为5 public static void bubbleSort(int arr[]) {// 用此方法给数组进行排序 int i = 0, temp = 0;// temp变量用来保存大数 int j = 0; boolean flag = false; for (j = 0; j < arr.length - 1; j++) { for (i = 0; i < arr.length - 1 - j; i++) {// i<5 下标是0-4 if (arr[i] > arr[i + 1]) {// 如果两个数是逆序的,就交换位置 flag = true;//flag为true说明两数逆序,需要交换位置 temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } if(flag==false) {//第二个for循环每循环一轮后进行比较,说明数组已经是有序的了可以退出循环了,整个for循环结束 break; }else { flag=false;//如果不满足flag==false的条件,就说明数组的两数之间发生了交换, // flag的值为true,为了优化,需要将flag再置为false } System.out.println("第" + (j + 1) + "次排序" + Arrays.toString(arr)); } } public static void main(String[] args) { int arr[] = { 7, 3, 22, 15, 8 }; bubbleSort(arr); } } 复制代码
以7,3,22,15,8为例:
第一轮排序后flag==ture满足
else { flag=false;//如果不满足flag==false的条件,就说明数组的两数之间发生了交换, // flag的值为true,为了优化,需要将flag再置为false }` 复制代码
所以flag=false,再开始第二轮排序
【22的位置被固定】3,7, 15, 8,22
第二轮排序后flag==ture满足
else { flag=false;//如果不满足flag==false的条件,就说明数组的两数之间发生了交换, // flag的值为true,为了优化,需要将flag再置为false }` 复制代码
所以flag=false,再开始第三轮排序 【15的位置被固定】3, 7, 8, 15, 22
第三轮排序后flag==false满足
if(flag==false) {//第二个for循环每循环一轮后进行比较,说明数组已经是有序的了可以退出循环了,整个for循环结束 break; } 复制代码
所以退出第一个for循环,结束数组排序。输出排序后的结果。
到此冒泡排序的讲解就结束了~~
欢迎大家来 “小乔的编程内容分享站”找小乔玩~
一起学习Java基础+算法~
还有更多资源等你来拿哦~