排序算法——冒泡排序系列及性能测试

缺乏、安全感 2022-12-13 04:58 144阅读 0赞

### 文章目录 ###

*   *   *  初识冒泡排序
         *  优化思路
         *   *  思路一
             *  思路二
         *  性能测试
         *  加餐（鸡尾酒排序）

### 初识冒泡排序 ###

排序算法常常作为学习算法的入门实践，而冒泡排序又是其中最简单的一种，我们今天的主题就是冒泡排序。它的基本思想就像鱼吐泡泡一样简单。  
  
  
想象有一条鱼在数组的最底端，每一轮，它就吐个泡泡，泡泡会从数组一端漂到另一端，在漂浮过程中，泡泡会捕获数组中**待排序的部分**中最大的元素，将其移动到最顶端，然后把这个元素从数组**待排序部分**中剔除。  
  
下一轮又从剩余的待排序元素中选一个最大的，用泡泡再次将其上浮到最顶端。如此一来，经过n轮吐泡泡。从数组最顶端往下，依次就是最大的元素，第二大的元素，第三大的元素…整个数组就是有序的了，当然，若想要逆序的话，每一轮就挑最小的元素冒泡上去就好了。

一轮冒泡的过程，是通过对相邻两个元素不断地比较和交换，来找到该轮冒泡中最大的元素，并将其移动到顶端的。  
  
  
具体过程是，想象一个指针，指针指向的元素称为**当前元素**。指针先指向第一个元素，比较当前元素和下一个元素之间的大小，若当前元素比下一个元素大，则交换当前元素和下一个元素。并把指针后移一个位置，继续和下一个元素比较，一直比到最后一个元素。这样，就完成了第一轮冒泡。第一轮冒泡完毕后，最右侧的元素就是最大的。第二轮冒泡，又从第一个元素开始，依次进行比较和交换，一直比到倒数第二个元素。第二轮结束，右侧倒数第二个元素就是第二大的…N轮冒泡后，整个数组就是从小到大有序的了

图解如下

假设准备对如下数组进行冒泡排序

![4c050af8d99d0a155e981ad44976d72e.png][]

第一轮冒泡

![9d2eb96dc3b3db70fb7261a1ba4aafaf.png][]

指针先指向第一个元素，比较当前元素与下一个元素，发现9比5大，那么交换二者

![1d55c5c93dd3b89d287191feee42a837.png][]

指针后移一位

![5f262becbc23c61659eaaffc34b91e7f.png][]

继续比较当前元素和下一个元素的大小，发现9比7大，交换之

![84557bc351200d91e9e607f060557983.png][]

指针继续后移一位，继续比较与交换，最终9被冒泡到最右端，第一轮冒泡结束

![a64fcac4ac21a5ac5c5d9b632e6a7439.png][]

第二轮冒泡开始，将指针放在第一个元素，开始重复第一轮的过程（注意第二轮只需要冒泡到倒数第二个位置即可，因为每一轮结束后，最右侧的有序序列的长度都会变长1位）

![4d321540994ca0de82317cd746677259.png][]

发现5比7小，则不交换。指针后移

![67841f1143d219878c26e2d128644368.png][]

发现7比3大，交换之

![4aa3ef73574c20a26f0ca090ce1166fb.png][]

指针后移

![ca17c7f07cdcc2b8a9220f53ce10ba14.png][]

发现7比1大，交换之…最后，8被冒泡到最右端

![bf7eeffd92944c81bc7132fad9ca4cf0.png][]

继续第三轮，7被冒泡到最右边

![5fb56a9f2e734cbbfb52beb788f60919.png][]

第四轮，6到了最右边

![89b959da100434412c88508be99a21b5.png][]

…

最后，整个数组有序

![6671646249013e360896b717eafd93ce.png][]

根据这个思路，写出代码如下

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

外层循环从数组最后一个位置开始，表示的是每一轮的终结位置（第一轮冒泡到最后一个位置停止，第二轮冒泡到倒数第二个位置停止，以此类推）。内层循环是一轮冒泡的过程，每轮冒泡，从第一个位置开始，依次与后一个位置进行比较和交换，一直进行到该轮冒泡的停止位置。当然，上述代码，只写出了核心部分的实现，并不完善。比如`bubbleSort`方法内，应该先判断`array`变量是否为`null`，`swap`方法内应该判断`array`是否为`null`，并检测`i`和`j`是否越界。

### 优化思路 ###

#### 思路一 ####

上面的冒泡排序的实现，实际还有可优化的空间。比如，若某一轮冒泡的过程中，没有发生任何元素交换。这就说明数组已经整体有序，则无需再进行后续的冒泡轮数。修改代码，只需要在每一轮冒泡开始前，新增一个布尔类型的标志变量`boolean sorted = true`，只要该轮冒泡发生过元素交换，就将`sorted`变量置为`false`。如此以来，在每轮冒泡结束后，新增一个判断逻辑，判断若`sorted`为`true`，则提前结束排序，写成代码如下。

public void bubbleSortV1(int[] array) { 
        boolean sorted;
    	for (int i = array.length - 1; i >= 0; i--) { 
            sorted = true;
    		for (int j = 0; j < i; j++) { 
    			if (array[j] > array[j + 1]) { 
    				swap(array, j , j + 1);
                    sorted = false;
    			}
    		}
            if(sorted) { 
                break;
            }
    	}
    }

#### 思路二 ####

如果说上面是粒度较大的优化（针对外层循坏的全局优化，满足条件时整个流程提前结束），则在更小粒度上还存在着优化空间（每轮冒泡过程中的优化）。原先的实现，每轮冒泡之后，最右侧有序序列的长度是依次加一的。即，第一轮冒泡，需要交换比较，直到最后一个位置；第二轮冒泡，需要交换比较，直到倒数第二个位置…然而，**每轮冒泡只需要将泡泡上浮到有序序列的边界即可终止**，我们可以根据每一轮的实际情况，来决定下一轮冒泡的停止位置。而不是每一轮都必须达到固定的停止位置。

比如有如下数组

![a77896862dd8444fe857eeb7018b3f60.png][]

第一轮冒泡后，数组变为

![8a6d1cb10c1384e3f18845475ab797a4.png][]

最后一次发生交换的是3和4的位置，之后都**只是进行了比较而并未发生交换**，说明4以后的都是有序序列了。那么，第二轮冒泡的终止位置可以不必到倒数第二个位置了，而可以只到**上一轮冒泡**发生的**最后一次交换的位置**（发生最后一次交换的位置的右侧，即是有序序列）。即，对于每一轮冒泡，新增了用于记录发生最后一次交换的位置的变量，用于指示下一轮冒泡的终止位置。写成代码如下

public void bubbleSortV2(int[] array) { 
    	boolean sorted;
    	int sortedSequenceBorder = array.length - 1;
    	while (true) { 
    		sorted = true;
    		int lastSwapPos = 0;
    		for (int i = 0 ; i < sortedSequenceBorder; i++) { 
    			if (array[i] > array[i + 1]) { 
    				swap(array, i, i + 1);
    				sorted = false;
    				lastSwapPos = i;
    			}
    		}
    		if (sorted) { 
    			break;
    		}
    		sortedSequenceBorder = lastSwapPos;
    	}
    }

注意，无论如何优化，冒泡排序的元素交换次数是不变的，优化措施减少的只是不必要的比较次数，给出如下示例，可自行验证

![580b6b4eb441bc225b1a168f57e3524d.png][]

### 性能测试 ###

理论上讲，由于后两种引入了优化措施，应该其效率要高于未优化的版本，即效率大小应为

`bubbleSortV2 > bubbleSortV1 > bubbleSort`

然而实际测试的时候发现，有时并不是如此，因为优化措施在每轮冒泡过程中加入了额外的判断，需要消耗一定性能的，并且如果待排序的数组，使用优化措施减少的无用比较的性能开销，小于引入额外判断造成的性能开销，即收益小于成本时，V1和V2的性能就不一定要高于未优化版本（并且还需要考虑到运行时机器的实际情况）。然而当数组规模较大时，优化措施能降低的比较次数较多，收益较高，则性能会优于未优化版本。

下面针对3个冒泡排序的版本，进行性能测试。测试使用随机生成的数组，数组规模从100，400，700…一直到14800（数组规模从100开始，规模依次递增300，共测试50组数组）。为了避免运行时机器的影响因素，对每组数组，重复测试20次，取性能平均值。绘制得到的性能折线图如下

![14a624fbcb1a5d5ec129ff81468c248f.png][]

可知，随着数组规模的增大，优化后的版本性能要明显好于未优化的版本，且V2版本性能略优于V1

### 加餐（鸡尾酒排序） ###

另，还有一种冒泡排序的变种，名为**鸡尾酒排序**，它的思想是双向冒泡，奇数轮从左到右，将最大的元素冒泡到最右侧，偶数轮从右到左，将最小的元素冒泡到最左侧。鸡尾酒排序在数组中间部分有序，而两端乱序时，能够取得较好的性能提升。下面是它的代码实现，和冒泡排序非常类似

public void cockTailSort(int[] array) { 
    		boolean moveRight = true;
    		int rightBorder = array.length - 1;
    		int leftBorder = 0;
    		boolean sorted = false;
    		while (!sorted) { 
    			sorted = true;
    			if (moveRight) { 
    				for (int i = leftBorder; i < rightBorder; i++) { 
    					if (array[i] > array[i + 1]) { 
    						swap(array, i, i + 1);
    						sorted = false;
    					}
    				}
    				rightBorder--;
    				moveRight = false;
    			} else { 
    				for (int i = rightBorder; i > leftBorder; i--) { 
    					if (array[i] < array[i - 1]) { 
    						swap(array, i, i - 1);
    						sorted = false;
    					}
    				}
    				leftBorder++;
    				moveRight = true;
    			}
    		}
    	}

将鸡尾酒排序纳入性能测试，看看它和普通冒泡排序的对比

![e41ac6b57ca90103b5a5b24f893fed39.png][]

可见鸡尾酒排序的性能要略优于普通冒泡排序

[4c050af8d99d0a155e981ad44976d72e.png]: /images/20221123/08096bd4d17e4174a99347e03ac92610.png
[9d2eb96dc3b3db70fb7261a1ba4aafaf.png]: /images/20221123/053dc888faee42a1ab546c6826476770.png
[1d55c5c93dd3b89d287191feee42a837.png]: /images/20221123/7dfcaebb9cdf42d89d82aa9ab0bf150c.png
[5f262becbc23c61659eaaffc34b91e7f.png]: /images/20221123/dfdc0f5454c44e978cf579d0e75ee015.png
[84557bc351200d91e9e607f060557983.png]: /images/20221123/29c1cd336e2b4e5b9ae5fb7493f82a10.png
[a64fcac4ac21a5ac5c5d9b632e6a7439.png]: /images/20221123/ac0b54b38bff4d51bdccb6a1933c69de.png
[4d321540994ca0de82317cd746677259.png]: /images/20221123/746bb02752d84980b7267eb00f5634f5.png
[67841f1143d219878c26e2d128644368.png]: /images/20221123/4c31388c31ab47aebdff4fe22f42487e.png
[4aa3ef73574c20a26f0ca090ce1166fb.png]: /images/20221123/8412742447c947309bf6d20794561f03.png
[ca17c7f07cdcc2b8a9220f53ce10ba14.png]: /images/20221123/735dcbbe57d040c3ab7419eb1ef7ea0f.png
[bf7eeffd92944c81bc7132fad9ca4cf0.png]: /images/20221123/36320f9cff404e2aa28b2482bc6fccfa.png
[5fb56a9f2e734cbbfb52beb788f60919.png]: /images/20221123/827524c2cb744b2abdddf6997477efc2.png
[89b959da100434412c88508be99a21b5.png]: /images/20221123/2bdcdf6e14da4920b3c0875ef82c64c2.png
[6671646249013e360896b717eafd93ce.png]: /images/20221123/d4f378adc12d4a9eacc5041896b530ba.png
[a77896862dd8444fe857eeb7018b3f60.png]: /images/20221123/af2b7a50b1854735b76267ef573aa4a8.png
[8a6d1cb10c1384e3f18845475ab797a4.png]: /images/20221123/54f55ddad94e497fbbc079b7d57d0079.png
[580b6b4eb441bc225b1a168f57e3524d.png]: /images/20221123/31dd4b222ca54b84b0882f4c6e885451.png
[14a624fbcb1a5d5ec129ff81468c248f.png]: /images/20221123/7ae9d1a7fcc64b88bc7fa89bb0c5af69.png
[e41ac6b57ca90103b5a5b24f893fed39.png]: /images/20221123/473b75be9d854d868d7f9f356e3d8f22.png