【Array】冒泡排序 || 杨辉三角

浅浅的花香味﹌ 2023-09-29 09:06 18阅读 0赞

### 一.冒泡排序 ###

这是一种简单实用的排序算法，今天我们来用Java代码结合数组实现冒泡排序

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oeS576K576KLmphdmE_size_18_color_FFFFFF_t_70_g_se_x_16][]

(1) 首先比较第一和第二个数，将小数放在前面，将大数放在后面。

(2)比较第2和第3个数，将小数 放在前面，大数放在后面。

(3)如此继续，知道比较到最后的两个数，将小数放在前面，大数放在后面，重复步骤，直至全部排序完成

### 规律 ###

1.在上面一趟比较完成后，最后一个数一定是数组中最大的一个数，所以**在比较第二趟的时候，最后一个数是不参加比较**的。

2.在第二趟比较完成后，倒数第二个数也一定是数组中倒数第二大数，所以**在第三趟的比较中，最后两个数是不参与比较**的。

3.**每一趟比较次数减少依次**

### 规律实现 ###

1.我们用引入中间量思想实现**交换数组中的两个元素位置（排序核心思想）**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oeS576K576KLmphdmE_size_20_color_FFFFFF_t_70_g_se_x_16][]

2.当我们比较到最后一轮时我们可以通过一次比较确定两个元素的位置，这样针对元素个数我们就可以少比较一轮。

例如：有n个需要排列的元素，我们需要比较**n-1**轮

3.比较一轮就可以确定一个元素的位置，所以比较几轮比较我们就确定了几个元素的位置，当我们比较下一轮时就会少一个要比较的元素

例如：比较了m轮我们就**确定了m个元素**的位置，而在每一轮中要比较的元素个数就变成了**n-1-m**

### 代码实现功能 ###

int[] arr= {9,8,3,1,2};
    int temp=0;   //中间值
    for(int j=0;j<arr.length-1;j++) {
    for(int i=0;i<arr.length-j-1;i++) {
    	if(arr[i+1]<arr[i]) {    //冒泡过程
    		temp=arr[i];        
    		arr[i]=arr[i+1];
    		arr[i+1]=temp;
    	}	
    }
    System.out.println("\n第"+(j+1)+"次排序");
    for(int i=0;i<arr.length;i++) {      //遍历完整数组 输出
    	System.out.print(arr[i]+"\t");
          }
        }

运行结果如下

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oeS576K576KLmphdmE_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

### **二.杨辉三角** ###

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oeS576K576KLmphdmE_size_8_color_FFFFFF_t_70_g_se_x_16][]

根据上述图片不难总结出如下

### 规律 ###

1.每一行**首尾都是1**

2.每一行非0的数都是**上一行对应位置（列）的数和前一个数的和**

3.**每行元素个数依次+1**

### 规律实现 ###

1.凡是**涉及到与行列类似的属性我们就要考虑使用二维数组**了，由于每行的元素个数不是统一的所以我们要这样创建数组 int\[\]\[\] arr=new int\[n\]\[\]; 这个n的值结合具体情况取他代表你的杨辉三角有几行

2.我们通过遍历数组，把遍历（从0开始遍历的）的次数用一个变量 i 体现出来-----**i+1**（这里是因为从0开始遍历所以要+1）的值就是每行元素的个数

arr\[i\]=new int\[i+1\];

3.遍历二维数组中的一维数组，把他首尾位置确定出来，赋值1给他们，如果不是首尾元素那就符合 规律2 这里我们可以用到**if语句**来一举两得

**if(j==0||j==arr\[i\].length-1) \{  
arr\[i\]\[j\]=1;  
\} else \{  
arr\[i\]\[j\]=arr\[i-1\]\[j\]+arr\[i-1\]\[j-1\];  
\}**

### 代码实现功能 ###

int[][] arr=new int[6][];   
          for(int i=0;i<arr.length;i++) {
        	arr[i]=new  int[i+1];       //给每一个一维数组开辟空间  不开就是null
        	  for(int j=0;j<arr[i].length;j++) {
        		if(j==0||j==arr[i].length-1) {       //arr[i].length-1*****  这是我经常错的点
        			arr[i][j]=1;
        		}  else {
        			arr[i][j]=arr[i-1][j]+arr[i-1][j-1];    //核心规律
        		}
        	  }
          }
          for(int i=0;i<arr.length;i++) {       //遍历完整数组 输出
        	  for(int j=0;j<arr[i].length;j++) {
        		  System.out.print(arr[i][j]+"*");
        	  }
        	  System.out.println();
          }

运行结果如下

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oeS576K576KLmphdmE_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

深夜码字不易，如果对理解起到帮助就给个三连吧~~~

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oeS576K576KLmphdmE_size_18_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/9a60bc51af77428aa8c1345567b960a6.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5oeS576K576KLmphdmE=,size_18,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oeS576K576KLmphdmE_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/3fe364c1df0d479e9d277a051e057b9b.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5oeS576K576KLmphdmE=,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oeS576K576KLmphdmE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/a806ae60ba124a6ca5e614416fd80f34.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5oeS576K576KLmphdmE=,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oeS576K576KLmphdmE_size_8_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/1bb238a4f9c9491eafd9bae9ee50b736.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5oeS576K576KLmphdmE=,size_8,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5oeS576K576KLmphdmE_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/a5e0127305b9411784b11ce11c803dee.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5oeS576K576KLmphdmE=,size_20,color_FFFFFF,t_70,g_se,x_16