面试官：手写一个冒泡排序，并对其改进

小鱼儿 2022-10-17 10:41 136阅读 0赞

> 核心思想(升序为例)：  
> 从首位置开始，依次比较前后两个数，如果前面的数比后面的数大，就交换两个数。这样第1轮结束后，最大的数就会移动到最后的位置。对剩余元素重复执行N-1次，整个数组有序。因为像空气上浮到水面，最大的元素会慢慢浮到最后，所以**冒泡**因此得名。

冒泡排序是比较简单的一种排序算法，核心思想就是比较相邻的两个数，但效率比较低所以可做一些优化。时间复杂度为O(N^2)，数据规模较小时可采用，但数据过大时就不建议采用冒泡了。

### **原始：** ###

public class MaopaoTest {
        public static void main(String[] args) {
            int[] arr = new int[]{3,2,6,8,7,5};
    
            System.out.println("排序前：");
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i]+" ");
            }
    
            //进行多少轮
            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]) {
                        //交换位置
                        swap(arr,j, j+1);
                    }
                }
            }
    
            System.out.println("\n排序后：");
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i]+" ");
            }
        }
    
        /**
         * 利用中间变量，交换位置
         * @param before
         * @param after
         */
        private static void swap(int[] arr,int before, int after) {
            int temp = arr[before];
            arr[before] = arr[after];
            arr[after] = temp;
        }
    }

按原始的写法，不管有没有排序好，每次都把所有元素两两比较一下，效率着实有点低，所以可做一些优化。

### **优化一：迭代轮次优化** ###

如果原数组在执行完某一轮后，整个数组已经有序，后面的轮次就没必要执行，可以针对这种情况做一次优化改进。

**改进方法：**  
如果某一轮没有发生过交换，说明数组已经有序，那么以后也不会发生交换，此时可以终止迭代。后续的轮次就不需要再去执行了，在代码中的体现就是跳出外循环。

public class MaopaoTest {
        public static void main(String[] args) {
            int[] arr = new int[]{3,2,6,8,7,5};
    
            System.out.println("排序前：");
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i]+" ");
            }
    
            //进行多少轮
            for (int i = 0; i < arr.length-1; i++) {
                //优化1：迭代轮次优化，flag做标记
                boolean flag = true;
    
                //每轮进行的循环次数
                for (int j = 0; j < arr.length - 1 - i; j++) {
                    if (arr[j] > arr[j+1]) {
                        //交换位置
                        swap(arr,j, j+1);
                        //发生过交换，做标记
                        flag = false;
                    }
                }
    
                //如果某一伦没有发生交换，说明有序，后续的轮次不再进行
                if(flag){
                    break;
                }
            }
    
            System.out.println("\n排序后：");
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i]+" ");
            }
        }
    
        /**
         * 利用中间变量，交换位置
         * @param before
         * @param after
         */
        private static void swap(int[] arr,int before, int after) {
            int temp = arr[before];
            arr[before] = arr[after];
            arr[after] = temp;
        }
    }

### **优化二：扫描范围优化** ###

上一轮最后交换的位置，在下一轮时，此位置后面的数也不会再发生交换。

**改进方法：**

记录每一次最后发生交换的位置，下一轮只需要扫描到此位置的前一个即可。

public class MaopaoTest {
        public static void main(String[] args) {
            int[] arr = new int[]{3,2,6,8,7,5};
    
            System.out.println("排序前：");
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i]+" ");
            }
    
            //优化2：扫描范围优化，记录每轮最后交换的位置,因为交换过后，后面的元素都是有序的，不需要扫描
            int len = arr.length - 1;
            int position = arr.length - 1;
    
            //进行多少轮
            for (int i = 0; i < arr.length-1; i++) {
                //优化1：迭代轮次优化，flag做标记
                boolean flag = true;
    
                //每轮进行的循环次数
                for (int j = 0; j < len; j++) {
                    if (arr[j] > arr[j+1]) {
                        //交换位置
                        swap(arr,j, j+1);
                        //发生过交换，做标记
                        flag = false;
                        //发生过交换，记录位置
                        position = j;
                    }
                }
    
                //重新赋值，下一轮最多扫描到这个位置
                len = position;
    
                //如果某一伦没有发生交换，说明有序，后续的轮次不再进行
                if(flag){
                    break;
                }
            }
    
            System.out.println("\n排序后：");
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i]+" ");
            }
        }
    
        /**
         * 利用中间变量，交换位置
         * @param before
         * @param after
         */
        private static void swap(int[] arr,int before, int after) {
            int temp = arr[before];
            arr[before] = arr[after];
            arr[after] = temp;
        }
    }