冒泡排序算法的逐步优化

╰半橙微兮° 2021-11-26 15:12 324阅读 0赞

# 冒泡排序算法的优化，一些场景效果差距巨大！！ #

# 代码都经过运行测试，可直接复制自行测试，思路比较重要，为重点 #

## 基本的冒泡算法代码如下： ##

public void basicSort(int[] array){
            int temp = 0;
            for (int i = 0; i < array.length - 1; i++) {
                for (int j = 0; j < array.length-i-1; j++) {
                    if(array[j]>array[j+1]){
                        temp = array [j+1];
                        array[j+1]=array [j];
                        array [j]=temp;
                    }
                }
            }
        }

***我们可以优化交换时使用差来交换，不声明变量（先不搞）***  
**冒泡的优化空间还存在很大的空间。**

## 1.第一版优化： ##

**例数组如：**  
**\[1, 2, 3 ,0, 4 ,5 ,6 ,7, 8, 9\]**  
**直观的看到数组中只有0不是有序的，需要把0交换到最前：**

**基本冒泡流程**

***1轮:***

1比2，不交换;

2比3，不交换;

3比0，交换   数组为\[1, 2, 0 ,3, 4 ,5 ,6 ,7, 8, 9\]

3比4，不交换；

4比5，不交换；

5比6，不交换；

6比7，不交换；

7比8，不交换；

8比9，不交换；

***2轮：***

1比2，不交换;

2比0，交换  数组为\[1, 0, 2 ,3, 4 ,5 ,6 ,7, 8, 9\]

2比3，不交换;

3比4，不交换；

4比5，不交换；

5比6，不交换；

6比7，不交换；

7比8，不交换；

***3轮：***

1比0，交换 数组为\[0, 1, 2 ,3, 4 ,5 ,6 ,7, 8, 9\]

1比2，不交换;

2比3，不交换;

3比4，不交换；

4比5，不交换；

5比6，不交换；

6比7，不交换；

**第三轮就可以看到数组已经有序了，但是循环还是会继续**

***4轮；。。。9轮；***

***基本冒泡代码：***

***运行结果：***  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTc1Njgw_size_16_color_FFFFFF_t_70][]

**这里就可以进行优化。**

### **思路：当我们完成一轮对比后没有任何数据进行交换，说明数组已经是有序的，外层循环就可以提前结束！！** ###

***第一版优化后的实现代码：***

@Test
        public void test() throws Exception {
            int[] temp = new int[]{1, 2, 3, 0, 4, 5, 6, 7, 8, 9};
            basicSort(temp);
            System.out.println(Arrays.toString(temp));
        }
    
        public void basicSort(int[] array) {
            int wheelCount = 0;
            int compareCount = 0;
            int temp;
            for (int i = 0; i < array.length - 1; i++) {
                //新的一轮默认为true
                boolean isSorted = true;
                for (int j = 0; j < array.length - i - 1; j++) {
                    if (array[j] > array[j + 1]) {
                        temp = array[j + 1];
                        array[j + 1] = array[j];
                        array[j] = temp;
                        //当发生任何数据交换，则数组不是有序的，设置为false
                        isSorted=false;
                    }
                    System.out.println("比较次数：" + ++compareCount + "");
                }
                System.out.println("轮次：" + ++wheelCount + "");
                //当没有数据交换时，isSorted为true，说明数组完成有序，提前结束。
                if(isSorted){
                    break;
                }
            }
        }

***运行结果：***

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTc1Njgw_size_16_color_FFFFFF_t_70 1][]

**可以看到明显差别：轮次在4次就结束了，比较次数也减少了，数据越多，优化效果更明显。此次优化主要优化了外层的轮次！**

## 第二版优化： ##

**还是以数组为例：\[1, 2, 3 ,0, 4 ,5 ,6 ,7, 8, 9\]**

***1轮:***

1比2，不交换;

2比3，不交换;

3比0，交换   数组为\[1, 2, 0 ,3, 4 ,5 ,6 ,7, 8, 9\]

3比4，不交换；

4比5，不交换；

5比6，不交换；

6比7，不交换；

7比8，不交换；

8比9，不交换；

***2轮：***

1比2，不交换;

2比0，交换  数组为\[1, 0, 2 ,3, 4 ,5 ,6 ,7, 8, 9\]

2比3，不交换;

3比4，不交换；

4比5，不交换；

5比6，不交换；

6比7，不交换；

7比8，不交换；

***N轮：。。。***

**问题：第一轮和第二轮的后6位重复比较，第一轮就知道了后六位是有序的，但是第二轮还是比较了6位。**

### **思路：就拿两轮来说，第一轮在比较第三次的时候，发送了数据交换，而后面的6次比较都没有发生数据交换，说明后面的6位数据是有序的，那么下轮的比较中是不是就可以就只比较到第三位，后面的比较可以省略！！** ###

***第二版优化后的实现代码：***

@Test
        public void test() throws Exception {
            int[] temp = new int[]{1, 2, 3, 0, 4, 5, 6, 7, 8, 9};
            basicSort(temp);
            System.out.println(Arrays.toString(temp));
        }
    
        public void basicSort(int[] array) {
            int wheelCount = 0;
            int compareCount = 0;
            //内层循环的初始比较次数
            int sorted = array.length-1;
            //最后一次数据交换的位置
            int lastIndex = 0;
            int temp;
            for (int i = 0; i < array.length - 1; i++) {
                //新的一轮默认为true
                boolean isSorted = true;
                for (int j = 0; j < sorted; j++) {
                    if (array[j] > array[j + 1]) {
                        temp = array[j + 1];
                        array[j + 1] = array[j];
                        array[j] = temp;
                        //当发生任何数据交换，则数组不是有序的，设置为false
                        isSorted=false;
                        //记录最后一次数据交换的位置（保持更新）
                        lastIndex=j;
                    }
                    System.out.println("比较次数：" + ++compareCount + "");
                }
                //内层循环结束后，把最后一次的位置给内层循环下次要比较的次数
                sorted=lastIndex;
                System.out.println("轮次：" + ++wheelCount + "");
                //当没有数据交换时，isSorted为true，说明数组完成有序，提前结束。
                if(isSorted){
                    break;
                }
            }
        }

***运行结果：***

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTc1Njgw_size_16_color_FFFFFF_t_70 2][]

**优化后，比较次数有明显的减少，在大量的数据更加明显！！**

--------------------

### **最后在模拟大量数据下的排序测试效果：** ###

**(因为想要看到明显差距：我们生成了500000条有序数据，更改了其中的一个值后的无序数组)；**

/**
         * 随机生成指定长度的数组
         * @param sum length
         * @return array
         */
        public int[] randomArray(int sum){
            int[] array = new int[sum];
            for (int i = 0; i < sum; i++) {
                array[i]=i+1;
            }
            array[5000]=1;
            return array;
        }

***测试（精度不是很准）：***

@Test
        public void test() throws Exception {
            int[] array = randomArray(500000);
            long date;
            long l = System.currentTimeMillis();
            basicSort(array);         //基本的冒泡
    //        upSort(array);          //第一版冒泡
    //        up2Sort(array);         //第二版冒泡
            long l1 = System.currentTimeMillis();
            date=l1-l;
            System.out.println("排序用时："+date);
        }

运行三个方法的结果（从上往下）：单位：毫秒

![20190723111335304.png][]

![20190723111357487.png][]

![20190723111415608.png][]

## **这种大量有序数组中的有一两个无序数据时，这几种的排序差距有点大，可自行测试** ##

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTc1Njgw_size_16_color_FFFFFF_t_70]: /images/20211126/3b741e26d3554d549cbbe5d70d1562db.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTc1Njgw_size_16_color_FFFFFF_t_70 1]: /images/20211126/46a6758586004ee7b73058143482e09d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTc1Njgw_size_16_color_FFFFFF_t_70 2]: /images/20211126/bdd501437ba64da2aaae879e97768336.png
[20190723111335304.png]: /images/20211126/f5ea08ff30b945899a7cdaea7a60188b.png
[20190723111357487.png]: /images/20211126/75833eff8fe14e4b99e19b93a3a780c2.png
[20190723111415608.png]: /images/20211126/2006ed41570d4085bbdfefac8b4a035a.png