日撸 Java 三百行（45 天: 冒泡排序：小巧好用的排序算法，数据的击鼓传花)

注意：这里是JAVA自学与了解的同步笔记与记录，如有问题欢迎指正说明

目录

一、关于冒泡排序及其思想

二、关于冒泡排序的代码思想及其代码实现

性能与特性分析

总结

---

一、关于冒泡排序及其思想

        冒泡排序是一种非常简单的排序，其思想相对简单，是简单排序中效率客观的方法中最容易代码编写的排序代码（个人观点），理论上只要记住其交换的思想，代码部分能很快敲出来。不同于前几日讲述的插入排序，冒泡排序是使用元素交换特性完成的，因此不再借鉴线性表的插入思想。

        冒泡的思想就是每回合找到当前数组未确定序列中最大的元素并且将这个元素交换到当前未确定序列数组的最右端，同最右端的确定序列合并，构成确定序列的一部分。即有不定序列\([0,k]\)与确定序列\([k+1,n)\)，每趟排序都基本能确定一个下标\(p\)使得\(L[p] =\max (L[i]) (i \in [0,k])\)，通过不断的交换最终使得使得\(p=k\)，从而削减不定序列为\([0,k-1]\)，扩充确定序列为\([k,n)\)。重复上列 *** 作直到不定序列为空，而确定序列为\([0,n)\)

        如果我们纵向观看这个 *** 作（确定序列在顶部，不定序列在底部），仿佛MAX就如同一个水泡，从底向上上浮，而在顶部与确定序列相遇即浮出水面，完成“ 冒泡 ”。可见这个算法的名称可谓是形象生动了。

        当然，上面的描述可能会给初学者带来一个误区：“ 是不是我们每回合都要挑选出一个不定序列中的最大数MAX呀 ”。其实不然！我们的目的在于“ 把最大数冒到最右端 ”，而不是“ 挑出最大元素，然后放到最右端 ”，这两句话是一样的吗？不一样，更准确说，前者是冒泡排序，后者是简单选择排序的思想（之后几天的学习内容）。后者存在一个在范围内求最大值的具体 *** 作，而前者把最大数冒到最右端其实并不用真的求出最大数。这就是交换思想的魅力了：

         （见上图）我们当前有\(\{1, 3, 6, 10, 7, 5, 9\}\)这样的序列，然后彼此相邻地对比元素，即有从小到大递增的下标\(i(0≤i≤n-2)\)，每次探讨\(L[i]\)与\(L[i+1]\)的大小关系，若前驱大于后继，则触发交换。那么这个例子中最开的\(L[0]\)与\(L[1]\)、\(L[1]\)与\(L[2]\)不会交换元素，而后续都会发生一次交换。

        可以看见，这种相邻交换思想就如同一个很小动态规范过程，每次\(L[i]\)与\(L[i+1]\)讨论交换信息的时候，元素\(L[i]\)本身就可能是前面\([0,i]\)的最优解，然后在本轮交换时就讨论了这个最优解对于当前解的贡献情况。发生了交换，则是认可了这个解的贡献并作为当前\([0,i+1]\)的最优解，若没交换，这是认定\(L[i+1]\)为当前\([0,i+1]\)的最优解。这就是相邻交换的传递性。宛如击鼓传花中人们相互传递一个物件一样，当然略有不同的就是，传给一个小伙子时如果这个人绝对自己有更“ 好 ”的物件时会抛弃之前传递的物件而掏出自己的物品开始传递。

二、关于冒泡排序的代码思想及其代码实现

         我们依旧将代码思想同代码一同讲解，这样即理解了代码，同时也方便我们后续能自己回忆思想而辅助完成代码的编写。

        通过逻辑分析，代码中需要不断遍历不确定序列部分。但是这里要注意一个细节：假如说不确定序列有\(m\)个的话，我们的指针只能遍历前\(m-1\)个。因为算法要求相邻元素交换，这个交换过程中存在下标+1的访问，因此指针不要指向有效范围的最后一个元素，以避免越界（这个对于经常编写代码的人来说应该不算难）而体现在下图就是我们的\(j\)指针遍历的蓝色范围。

        上图诠释了指针控制的基本思想，指针\(i\)取从最后一个元素到第正数二个元素的所有情况，并通过指针\(i\)构成上界，确定指针\(j\)的覆盖范围，在这个范围内，指针\(j\)从小到大遍历，并且不断进行相邻元素的交换 *** 作。这个过程中指针\(i\)循环次数即为趟数。代码对这个过程的实现如下：

    for (int i = length - 1; i > 0; i--) {
		for (int j = 0; j < i; j++) {
				if (data[j].key > data[j + 1].key) {

					// Swap.

				} // Of if
			} // Of for j
	} // Of for i

         上图所示的交换结果如下：

         进一步，我们来看第二趟的情况：

         可见第二趟过程中，刚好最大的元素已经在预定的位置了，因此这次 *** 作的交换只完成一部分无序序列内部的 *** 作，进一步完善了第一趟排序导致的部分大小顺序问题。

        然后第三趟：

         第三趟与第二趟有相同的情况。

         而当我们进行到第四趟时：

         可以发现已经没有交换 *** 作进行了，仔细观察可以发现，因为我们的无序序列部分已经有序了。可以预想，在接下来的趟数里面，随着\(j\)指针范围的缩小，新范围内也依旧有序。所以到这个时候我们的整个数组已经有序，后面的 *** 作完全可以跳过了。因此，冒泡中暗藏一个小剪枝 *** 作：在一次对于无序序列的交换过程中若无任何交换发生，那么就提前结束算法（Premature），避免不必要的时间开销。可见这个算法对于基本有序且元素大多在排序后的位置情况下复杂度是相对比较低的。

        至此我们可以贴出冒泡的代码和单元测试了：

	/**
	 *********************
	 * Bubble sort.
	 *********************
	 */
	public void bubbleSort() {
		boolean tempSwapped;
		DataNode tempNode;
		for (int i = length - 1; i > 0; i--) {
			tempSwapped = false;
			for (int j = 0; j < i; j++) {
				if (data[j].key > data[j + 1].key) {
					// Swap.
					tempNode = data[j + 1];
					data[j + 1] = data[j];
					data[j] = tempNode;

					tempSwapped = true;
				} // Of if
			} // Of for j

			// No swap in this round. The data are already sorted.
			if (!tempSwapped) {
				System.out.println("Premature");
				break;
			} // Of if

			System.out.println("Round " + (length - i));
			System.out.println(this);
		} // Of for i
	}// Of bubbleSort

	/**
	 *********************
	 * Test the method.
	 *********************
	 */
	public static void bubbleSortTest() {
		int[] tempUnsortedKeys = { 1, 3, 6, 10, 7, 5, 9 };
		String[] tempContents = { "if", "then", "else", "switch", "case", "for", "while" };
		DataArray tempDataArray = new DataArray(tempUnsortedKeys, tempContents);

		System.out.println(tempDataArray);

		tempDataArray.bubbleSort();
		System.out.println("Result\r\n" + tempDataArray);
	}// Of bubbleSortTest

         此数据与模拟图中的例子一致，经过对比，完全一致！

         在冒泡排序中存在一段数据交换的代码，我们使用了一个中间元素tempNode来辅助实现data[j + 1]与data[j]的交换。这个 *** 作是每个初学代码的人都会的基本功。而我这里想给大家分享一个小tips，实现无中间变量的数据交换——使用异或来完成交换：

a = a ^ b;
b = a ^ b;
a = a ^ b;

         怎么样？这个其实谈不上有多大优化，而且这个只能针对整型。那为什么要这么做呢？其实就是“ 好玩 ”。通过体会这个技巧你能打开你对于位运算新世界的大门。（这其实也是位运算较基础的内容，会的大佬们当我没说吧(￣▽￣)）

性能与特性分析

        冒泡作为简单排序，空间复杂度依旧是\(O(1)\)；最糟糕的情况复杂度为\(O(N^2)\)，即完全逆序时，当有\(N\)个元素逆序，第一趟会执行\(N-1\)次判断，第二次会执行\(N-2\)次判断，不难得到总的比较次数为\(\sum_{i=1}^{n}n-i = \frac{n(n-1)}{2}\)，交换次数为\(\sum_{i=1}^{n}3(n-i) = \frac{3n(n-1)}{2}\)；最好情况复杂度为\(O(N)\)：即全部有序时，初次判断循环无序序列时便没有发生交换，触发早熟返回。整体平均复杂度为\(O(N^2)\)。

        冒泡排序算法是一个稳定的排序算法，因为在每次交换时遇到相同的元素并不会触发交换，因此相同值的元素之间的相对关系是可以保持的。并且在刚刚代码逻辑中已经分析过了，冒泡排序算法在原始数组基本有序且元素位置基本处于最终排序后的位置上的时候，复杂度是比较可观的。

        同时因为冒泡排序的交换特性总是针对相邻元素的，下标并没突然的跨越，而链表是可以在已知指针的情况下快速实现结点的交换 *** 作，而在交换了结点后继续维持指针的正常增加也是可以实现的，因此这个算法是可针对链表的，因此冒泡对于顺序表与链表都具有适用性。

        在排序中途停下来观察整个线性表（采用大元素向右冒泡），这个时候右端确定序列的任意元素都比左端不定序列中的元素要大，而且确定序列中的任意一个元素所在的下标位置就是排序结束后的它的最终位置。

总结

        冒泡排序是一个非常小巧好用的排序算法。我在当年大一的时候，学习的语言很有限而且还不会调用库，遇到需要的排序内容都是先手敲一个冒泡。再加上当时刷题频繁，写的练得多了，敲冒泡的代码也变得快了起来，可以说是信手拈来了。后来实际参与的项目多了，刷题时间没那么多了，学习的语言也更高级了，库也丰富了，渐渐没怎么手敲过排序算法了。但是我现在对于冒泡的“  感情 ” 还是有的。

        但是这样就断言那段大一的时光没意义吗？我想不是这样。各种调用库的诞生是为了帮你屏蔽底层逻辑而让你专注关心更需要解决的问题本身，但是这绝无说这些库、轮子内部的实现没必要学习了。一方面，手敲这些代码能更生动体会到代码的逻辑，这是一种逻辑学习，这对于之后以小见大实现大型项目的算法有很好的的启示作用；另一方面，试着在敲写这些代码的时候去联想可能的改进也是一种学习的过程（比如冒泡就可以改进成双向冒泡哟）

        最后嘛。要说为什么当年喜欢敲冒泡但不是其他简单的排序？可能当时我本科的教材里我看冒泡是所有排序代码中最短的，感觉好抄吧...  ━(￣ー￣*|||━━