排序之一：冒泡排序

• **介绍 **
  冒泡排序法又称为交换排序，其比较方式由第一个元素开始，比较相邻元素大小，若大小顺序有误，则对调后再进行下一个元素的比较。如此扫描过一次后就可确保最后一个元素是位于正确的顺序。接着再进行第二次扫描，直到完成所有元素的排序关系为之。
• 演示
  代码如下：

    private static void bubbleSort() {
        int data[] = {9, 6, 3, 2, 4, 5, 1, 8, 7};
        int i, j, tmp;
        for (i = data.length - 1; i > 0; i--) {
            for (j = 0; j < i; j++) {
                if (data[j] > data[j + 1]) {
                    tmp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = tmp;
                }
            }
        }
    }

打印结果：

冒泡排序打印信息.png

• 分析
  1. 最坏情况及平均情况均需比较n(n-1)/2次；时间复杂度为O(n²)，最好情况只需要完成一次扫描，发现没有做交换的操作则表示排序已经完成，所以只做了n-1次比较，是复杂度为O(n)。
  2. 由于冒泡排序为相邻两者相互比较对调，并不会更变其原本排序的顺序，所以是稳定排序法。
  3. 只需一个额外的空间，所以空间复杂度为最佳。
  4. 冒泡排序法适用于数据量小或者有部分数据已经排序过的情况。
• 优化
  通过上边的演示可以看出冒泡排序法有一个缺点，就是不管数据是否已经排序完成都会固定执行n(n-1)/2次，所以需要在排序中增加标记来提前中断程序，以此提高执行效率，代码如下：

    private static void bubbleSort() {
        int data[] = {9, 6, 3, 2, 4, 5, 1, 8, 7};
        int i, j, tmp, flag;
        for (i = data.length - 1; i > 0; i--) {
            flag = 0;    // flag 用来判断是否有执行
            for (j = 0; j < i; j++) {
                if (data[j] > data[j + 1]) {
                    tmp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = tmp;
                    flag++;    // 如果有执行过交换，则flag不为0
                }
            }
            if (flag == 0){
                break;    // 如果没有发生过交换就退出
            }
        }
    }

• 后记
  通过比较会发现一个有意思的现象，冒泡排序每次扫描都会确定后边的元素为目标顺序，而选择排序每次都扫描都会确定前边的元素为目标顺序。

---

其他排序：插入排序、选择排序、希尔排序、快速排序、基数排序