[数据结构与算法]09 冒泡排序( Java 版)

深藏阁楼爱情的钟 2023-07-09 11:26 7阅读 0赞

当你想到冒泡的时候,第一反应是什么?  
我这个人比较喜欢可口可乐,所以当看到冒泡,我的第一反应就是喝可乐的时候,有一个个的小泡泡冒出来,如果你仔细观察过的话,会看到这个小泡泡刚开始很小,但是等冒上来的时候,就比较大了.

上面大概就是一个描述,咱们根据上面的描述,详细说说原理:

*  1 ,比较相邻的元素.如果第一个比第二个大,就交换他们两个
 *  2 ,对接下来的每一对相邻元素都做同样的比较,从开始第一对到结尾的最后一对.  
    还记得第 1 条嘛?如果第一个比第二个大,那么就交换他们两个,对不对?所以,这样一轮结束之后,最后一个值是这些数中最大的值.
 *  3 ,针对所有的元素重复 1,2 的步骤,除了最后一个元素.  
    因为最后一个元素咱们已经确定了是最大的了,所以接下来的排序就不再担心了.
 *  4 ,持续 1,2,3 直到所有排序完毕.

看完原理之后,我们就能知道,冒泡排序就是将大的元素向后调,比较发生在两个元素之间,交换也是发生在这两个元素之间,也就是说,假设第一个数小于第二个数,那么接下来第一个数总是在第二个数前面,相对位置总是不变的.  
所以,我们说冒泡排序是一种稳定的算法.  
当然了,冒泡排序也可以将小的元素向后调,这些都取决于你怎么制定规则,你最大,你说了算~

上面介绍完毕了,咱们就直接上代码来看看.

/** * 冒泡排序实现 * @author 郑璐璐 * @date 2020-1-19 08:49:34 */
    public class Bubble { 
        public static void bubbleSort(int[] arr,int n){ 
             // 定义变量
            int i,j;
    
            for (i=0;i<n;i++){ 
            
                for (j=1;j<n-i;j++){ 
                    // 如果前面的数字,大于后面的数字,则进行交换
                    if (arr[j-1]>arr[j]){ 
                        int temp;
                        temp = arr[j-1];
                        arr[j-1] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
        }
        public static void main(String[] args){ 
            int[] arr ={ 1,8,95,45,78,56,23,456,741,16};
    
            bubbleSort(arr,arr.length);
    
            for (int i : arr) { 
                System.out.println(i);
            }
        }
    }

上面的就能实现冒泡排序,但是在写这篇博客,看书的时候,发现了一个很巧的方法,我也贴出来:

package com.anomalous.algorithm;
    
    /** * 冒泡排序实现 * @author 郑璐璐 * @date 2020-2-29 09:36:00 */
    public class Bubble { 
        public static void bubbleSort(int[] arr,int n){ 
            // 临时变量
            int temp = 0;
            // 标识变量,表示是否进行过交换
            boolean flag = false;
            for (int i = 0; i < arr.length - 1; i++) { 
    
                for (int j = 0; j < arr.length - 1 - i; j++) { 
                    // 如果前面的数比后面的数大,则交换
                    if (arr[j] > arr[j + 1]) { 
                        // 改变标识变量为 true
                        flag = true;
                        temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
                
                // 在一趟排序中,一次交换都没有发生过
                if (!flag) { 
                    break;
                } else { 
                    // 重置 flag ,进行下次判断
                    flag = false;
                }
            }
        }
        public static void main(String[] args){ 
            int[] arr ={ 1,8,95,45,78,56,23,456,741,16};
    
            bubbleSort(arr,arr.length);
    
            for (int i : arr) { 
                System.out.println(i);
            }
        }
    }

如果仔细看的话,你会发现引入了一个标识变量.  
这个标识变量有什么作用呢?如果你感兴趣可以运行一下程序,观察一下比较次数,会发现第二种方法程序的运行次数是比第一次的运行次数少的.  
为什么呢?你想想,其实最后一趟排序的时候,整体已经排好了,但是第一种方法会再次进行排序,第二种因为有标识变量的存在,如果一次交换都没有发生过,说明此时整个数组已经有序,所以不会再进行排序一次.  
只是因为多了一个标识变量,就节省了时间,这种思路,很巧妙~

以上,就是想要分享的内容了.  
感谢您的阅读哇~