一、冒泡排序

1.1 冒泡排序基础【必会知识】

  冒泡排序是比较基础的排序算法之一，其思想是相邻的元素两两比较，较大的数下沉，较小的数冒起来，这样一趟比较下来，最大(小)值就会排列在一端。整个过程如同气泡冒起，因此被称作冒泡排序。
  冒泡排序的步骤是比较固定的：

1>比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2>每趟从第一对相邻元素开始，对每一对相邻元素作同样的工作，直到最后一对。
3>针对所有的元素重复以上的步骤，除了已排序过的元素(每趟排序后的最后一个元素)，直到没有任何一对数字需要比较。

此处引用网上一张比较经典的gif来展示冒泡排序的整个过程：

  冒泡排序的常规实现代码如下：

	public static void bubbleSort(int[] arr) {
		/*判断数组为空或为一个元素的情况，即边界检查*/
		if (arr == null || arr.length < 2) {
			return;
		}
		
		/*规定每次两两比较的末尾元素的位置，最多为数组的最后一个位置*/
		for (int end = arr.length - 1; end > 0; end--) {
			/*从第一个元素开始，两两进行比较，如果前面的元素大于后面的
			  元素，就交换，最终的结果就是最大的数在最后面
			*/
			for (int i = 0; i < end; i++) {
				if (arr[i] > arr[i + 1]) {
					swap(arr, i, i + 1);
				}
			}
		}
	}

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

1.2 冒泡排序优化

  上个章节介绍了冒泡排序的常规实现，但是这种最简单的排序是存在着不必要的比较动作的。稍微修改上述代码，就可以查看每次比较后的结果：

        int[ ] array=new int[ ]{5,2,3,9,4};
        /*外循环为排序趟数，array.length个数进行array.length-1趟 */
        for(int i=0;i<array.length-1;i++){
        	/*内循环为每趟比较的次数，第i趟比较array.length-i次 */
            for(int j=0;j<array.length-1-i;j++){
            	 /*相邻元素比较，若满足条件则交换（升序为左大于右，降序反之） */
                if(array[j]>array[j+1]){
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                }
                /*查看每趟比较后的数组元素*/
                System.out.println("第 "+(i+1)+" 趟，第 "+(j+1)+" 次比较后的结果：");
                for(int k=0;k<array.length;k++){
                    System.out.print(array[k]+" ");
                }
                System.out.println();
            }
        }

该代码的输出结果为：

第 1 趟，第 1 次比较后的结果：
2 5 3 9 4
第 1 趟，第 2 次比较后的结果：
2 3 5 9 4
第 1 趟，第 3 次比较后的结果：
2 3 5 9 4
第 1 趟，第 4 次比较后的结果：
2 3 5 4 9
第 2 趟，第 1 次比较后的结果：
2 3 5 4 9
第 2 趟，第 2 次比较后的结果：
2 3 5 4 9
第 2 趟，第 3 次比较后的结果：
2 3 4 5 9
第 3 趟，第 1 次比较后的结果：
2 3 4 5 9
第 3 趟，第 2 次比较后的结果：
2 3 4 5 9
第 4 趟，第 1 次比较后的结果：
2 3 4 5 9
 

从上面的测试结果可以看出，从第2趟第3次比较后，数组元素已经处于有序状态，此后所有的比较都不必进行。

1.2.1 外循环优化
  第一种优化就基于上面的测试结果来进行，如果某次比较过程中，发现没有任何元素移动，则不再进行接下来的比较。具体的做法是在每趟比较时，引入一个boolean型变量isSwap，来判断下次比较还有没有必要进行。示例代码如下：
 

        int[ ] array=new int[ ]{5,2,3,9,4};
        /*外循环为排序趟数，array.length个数进行array.length-1趟 */
        for(int i=0;i<array.length-1;i++){
        	boolean isSwap=false;
        	/*内循环为每趟比较的次数，第i趟比较array.length-i次 */
            for(int j=0;j<array.length-1-i;j++){
            	 /*相邻元素比较，若满足条件则交换（升序为左大于右，降序反之） */
                if(array[j]>array[j+1]){
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                    isSwap=true;
                }
                /*查看每趟比较后的数组元素*/
                System.out.println("第 "+(i+1)+" 趟，第 "+(j+1)+" 次比较后的结果：");
                for(int k=0;k<array.length;k++){
                    System.out.print(array[k]+" ");
                }
                System.out.println();
            }
            /*如果没有交换过元素，则已经有序，不再进行接下来的比较*/
            if(!isSwap){
            	break;
            }
        }

  测试结果如下：

第 1 趟，第 1 次比较后的结果：
2 5 3 9 4
第 1 趟，第 2 次比较后的结果：
2 3 5 9 4
第 1 趟，第 3 次比较后的结果：
2 3 5 9 4
第 1 趟，第 4 次比较后的结果：
2 3 5 4 9
第 2 趟，第 1 次比较后的结果：
2 3 5 4 9
第 2 趟，第 2 次比较后的结果：
2 3 5 4 9
第 2 趟，第 3 次比较后的结果：
2 3 4 5 9
第 3 趟，第 1 次比较后的结果：
2 3 4 5 9
第 3 趟，第 2 次比较后的结果：
2 3 4 5 9

从上面的测试结果可以看出，已经对排序过程进行了优化，因为没有进行第4趟比较。也许有人会有疑问“第2趟比较结束后，数组已经有序了，为什么还要进行第3次比较”？之所以对此有疑问，可能是没太清楚isSwap变量的作用，该变量的作用是“假如本趟比较过程中没有交换发生，则不必进行下一趟比较”，在第2趟比较过程中，发生了交换动作，所以第3趟比较仍会进行。