排序算法-冒泡排序

排序算法系列博客：
直接插入排序
希尔排序
简单选择排序
堆排序
冒泡排序
快速排序
归并排序
计数排序
基数排序

九大排序排序是数据结构体系中最重要的内容之一，这一块必须要非常熟练的掌握，应该做到可以立马写出每个排序的代码，有多种实现方法的必须多种都能很快写出来，当然对各个排序的性能的了解也是基础且重要的。我们先对排序这一块进行一个整体的把握。

• 内排序：在对待排序数据存放在内存中进行的排序过程。是我们主要讨论与学习的重点。
• 外排序：待排数据量太大，无法一次性将所有待排序数据放入内存中，在排序过程中需要对磁盘等外部储存器进行访问。不是我们谈论与学习的重点，但也要通过相关资料或书籍了解其基本原理。
• 比较排序：排序过程中需要对数据关键字进行比较。
• 非比较排序：排序过程中不需要对数据关键字进行比较。
• 排序算法的稳定性：在每一次单趟排序后，相同关键字的相对顺序不变。（后面讲到了再具体解释）

所有讲解都以升序为例（降序完全就是改个符号的问题啦），本篇先讲几个简单的，复杂些的后面每个单独写。

冒泡排序

待排序数组: 42 ,13 ,15 ,28 ,23 ,17 ,14
冒泡相对算是最简单的排序了。思想就是：冒泡，就像水中的气泡，越往上泡泡约大，每一趟排序，都确定下来一个最大值，也就是冒出一个大泡泡。太多的解释不在赘述，网上都是。看下图：

解析冒泡排序过程：
1.第一趟排序

• 42和13比较，42>13 ，所以，42和13交换：
  

• 42和15比较，42>15，所以，42和15交换：
  

• 42和28比较，42>28，所以，42和28交换：
  

• 42和23比较，42>23，所以，42和23交换：
  

• 42和17比较，42>17，所以，42和17交换：
  

• 42和14比较，42>14，所以，42和14交换：
  

• 42和15比较，42>15，所以，42和15交换：
  

到此：第一趟排序结果就出来了，也就是j=0那一行的排序结果。得到的最后42，这个值，是有序区，无需继续比较大小，排序。
2.第二趟排序
同理，得出第二趟排序结果。【最后那个42是有序区，第二趟排序，就不需要比较这个值了】
第二趟结果：

这里有序区就是（28，42）。继续第三趟排序时候，就可以不比较这几个值了。
3.第三趟排序
同理，得出第三趟排序结果。【最后那个 28，42 是有序区，第三趟排序，就不需要比较这几个值了】
第三趟结果：

这里有序区就是（23，28，42）。继续第四趟排序时候，就可以不比较这几个值了。
。。。等等。如此，就能得出最后结果。应该能理解他的过程了吧？

下面上代码（Java实现）

/**
 * 冒泡排序测试代码 - 优化前
 * 存在问题：产生很多不必须要继续比较的操作
 * 就是上文中说的有序区，这里代码依旧进行了比较操作，这是多余的。
 * @param num
 * @return
 */
public int[] maoTest1(int[] num) {
    // 数组长度
    int len = num.length;
    // 临时变量，用于ab交换值
    int temp = 0;   
    // 外循环- 一行行往下走
    for (int j = 0; j < len; j++) {
        // 内循环-两两冒泡，把大的值冒到最后-确定下来排序完的一行的结果
        for (int i = 0; i < len - 1; i++) {
            if (num[i] > num[i + 1]) {
                temp = num[i];
                num[i] = num[i + 1];
                num[i + 1] = temp;
            }
        }
    }    
    return num;
}

/**
 * 冒泡排序 - 优化后
 * @param num
 * @return
 */
public int[] maoTest2(int[] num) {
    // 数组长度
    int len = num.length;
    // 临时变量，用于ab交换值
    int temp = 0;  
    // 外循环- 一行行往下走
    for (int j = 0; j < len; j++) {
        // 内循环-两两冒泡，把大的值冒到最后-确定下来排序完的一行的结果
        for (int i = 0; i < len - 1 - j; i++) {
            if (num[i] > num[i + 1]) {
                temp = num[i];
                num[i] = num[i + 1];
                num[i + 1] = temp;
            }
        }       
    }   
    return num;
}