Java教程

【视频+图文+动画】详解冒泡排序(万字长文,超级详细~~)

本文主要是介绍【视频+图文+动画】详解冒泡排序(万字长文,超级详细~~),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

冒泡排序是排序算法中最易理解的一种排序方法。 今天就让我们以非常容易理解的视频+图文+动画的形式来学习 我们的入门排序算法:冒泡排序

点击这里看【时间、空间复杂度的详解】

点击这里快速选取适合你的算法入门书籍

一、视频讲解冒泡排序

点击这里即可去B站观看~

二、冒泡排序的思想

思想:

从前到后(即从下标较小的元素开始依次比较相邻元素的值,若发现逆序则交换位置,使值较大的元素逐渐从前移向后部eg:

待排序的数:7,3,22,15,8

根据冒泡排序的思想:

  1. 首先我们应该比较7和3是否是逆序的: 若逆序则交换这2个数的位置,因为7>3,它们的位置是逆序的故交换位置 交换后:7,3, 22,15,8   ⇒  3,7,22,15,8
  2. 比较7和22是否是逆序的: 若逆序则交换这2个数的位置,因为7<22,它们的位置是顺序的。故不用交换位置 顺序仍为:3,7,22, 15,8   ⇒  3,7,22, 15,8
  3. 以此类推,思路分析会进行详细分析。

三、冒泡排序的动画演示及思路分析

动画演示:

点这里去可视化网站

在这里插入图片描述

思路分析:

  1. 第一轮排序:22的位置被固定
  • 7和3比较,若逆序则交换位置。因为7>3两数是序的,所以交换位置: 7,3, 22,15,8   ⇒  3,7, 22,15,8
  • 7和22比较,若逆序则交换位置。因为7<22两数是序的,所以交换位置: 3, 7, 22, 15,8   ⇒   3, 7, 22, 15,8
  • 22和15比较,若逆序则交换位置。因为22>15两数是序的,所以交换位置: 3,7, 22,15, 8   ⇒   3,7, 15,22, 8
  • 22和8比较,若逆序则交换位置。因为22>8两数是序的,所以交换位置: 3,7, 15, 22,8   ⇒  3,7, 15, 8,22

第一轮排序后的结果:【22的位置被固定】3,7, 15, 8,22

  1. 第二轮排序:15的位置被固定
  • 3和7比较若逆序则交换位置。因为3<7两数是序的,所以交换位置: 3,7, 15, 8,22   ⇒   3,7, 15, 8,22
  • 7和15比较若逆序则交换位置。因为7<15两数是序的,所以交换位置: 3, 7, 15, 8,22   ⇒   3, 7, 15, 8,22
  • 15和8比较若逆序则交换位置。因为15>8两数是序的,所以交换位置: 3, 7, 15, 8, 22   ⇒   3, 7, 8, 15, 22

第二轮排序后的结果:【15的位置被固定】3, 7, 8, 15, 22

  1. 第三轮排序:8的位置被固定
  • 3和7比较若逆序则交换位置。因为3<7两数是序的,所以交换位置: 3,7, 8, 15,22   ⇒   3,7, 8, 15,22
  • 7和8比较若逆序则交换位置。因为7<8两数是序的,所以交换位置: 3, 7, 8, 15,22   ⇒   3, 7, 8, 15,22

第三轮排序后的结果:【8的位置被固定】:3, 7, 8,15, 22

  1. 第四轮排序:7的位置被固定
  • 3和7比较若逆序则交换位置。因为3<7两数是序的,所以交换位置: 3,7, 8,15,22   ⇒   3,7, 8,15,22

第四轮排序后的结果:【7的位置被固定】:3, 7, 8,15, 22

排序到此结束

思路总结 :

  1. 以上面的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

四、冒泡排序的代码+代码优化+代码详解

代码--————多个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变量用来保存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);
	}

}

复制代码

结果:

在这里插入图片描述

优化代码(版本1)--————两个for循环嵌套控制排序:

优化分析:

第一轮排序: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-3j < 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);
	}
}

复制代码

结果:

在这里插入图片描述

优化代码(版本2)--————两个for循环嵌套+标志控制排序:

优化分析:

当第二轮排序完成后,数组已经是有序的。

但是没有一个标志去告诉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);
	}

}

复制代码

结果:

在这里插入图片描述

代码详解(优化版本2)

以7,3,22,15,8为例:

  1. 第一轮排序:22的位置被固定
  • 7和3比较,若逆序则交换位置。因为7>3两数是序的,所以交换位置:flag==true 7,3, 22,15,8   ⇒  3,7, 22,15,8
  • 7和22比较,若逆序则交换位置。因为7<22两数是序的,所以交换位置:flag==false第一轮排序完成后才判断flag的值) 3, 7, 22, 15,8   ⇒   3, 7, 22, 15,8
  • 22和15比较,若逆序则交换位置。因为22>15两数是序的,所以交换位置:flag==true 3,7, 22,15, 8   ⇒   3,7, 15,22, 8
  • 22和8比较,若逆序则交换位置。因为22>8两数是序的,所以交换位置:flag==true 3,7, 15, 22,8   ⇒  3,7, 15, 8,22

第一轮排序后flag==ture满足

else {
		flag=false;//如果不满足flag==false的条件,就说明数组的两数之间发生了交换,
//				flag的值为true,为了优化,需要将flag再置为false
	 }`
复制代码

所以flag=false,再开始第二轮排序

【22的位置被固定】3,7, 15, 8,22

  1. 第二轮排序:15的位置被固定
  • 3和7比较若逆序则交换位置。因为3<7两数是序的,所以交换位置:flag==false第二轮排序完成后才判断flag的值3,7, 15, 8,22   ⇒   3,7, 15, 8,22
  • 7和15比较若逆序则交换位置。因为7<15两数是序的,所以交换位置:flag==false第二轮排序完成后才判断flag的值) 3, 7, 15, 8,22   ⇒   3, 7, 15, 8,22
  • 15和8比较若逆序则交换位置。因为15>8两数是序的,所以交换位置:flag==true 3, 7, 15, 8, 22   ⇒   3, 7, 8, 15, 22

第二轮排序后flag==ture满足

else {
		flag=false;//如果不满足flag==false的条件,就说明数组的两数之间发生了交换,
//				flag的值为true,为了优化,需要将flag再置为false
	 }`
复制代码

所以flag=false,再开始第三轮排序 【15的位置被固定】3, 7, 8, 15, 22

  1. 第三轮排序
  • 3和7比较若逆序则交换位置。因为3<7两数是序的,所以交换位置:flag==false第三轮排序完成后才判断flag的值3,7, 8, 15,22   ⇒   3,7, 8, 15,22
  • 7和8比较若逆序则交换位置。因为7<8两数是序的,所以交换位置:flag==false第三轮排序完成后才判断flag的值) 3, 7, 8, 15,22   ⇒   3, 7, 8, 15,22

第三轮排序后flag==false满足

if(flag==false) {//第二个for循环每循环一轮后进行比较,说明数组已经是有序的了可以退出循环了,整个for循环结束
				break;
			}
复制代码

所以退出第一个for循环,结束数组排序。输出排序后的结果。

在这里插入图片描述

到此冒泡排序的讲解就结束了~~

欢迎大家来 “小乔的编程内容分享站”找小乔玩~

一起学习Java基础+算法~

还有更多资源等你来拿哦~

在这里插入图片描述

这篇关于【视频+图文+动画】详解冒泡排序(万字长文,超级详细~~)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!