老狗啃骨头之算法-冒泡排序

冒泡排序（Bubble Sort）

  冒泡排序是交换排序，是一种简单直观的排序算法。

  冒泡的算法原理是逐次循环遍历，比较两个相邻的元素，将小的（或大的）往前调。这样，每一轮都能得到一个最小的（或最大的），剩下的重复这个操作，最后完成排序。这个算法的名字，每轮这个逐个对比置换，很像那种气泡浮起，从水底慢慢浮到上面的样子，往上越晃荡越大，故曰“冒泡”。

1：从一端开始，比较相邻的元素，将大的置换至后面；
2：逐次对后续的相邻元素做行为1，直至最后；
3：除最后一个元素，剩余数据样本持续1、2、3步骤，直至排序结束。

import java.util.Arrays;

/**
 * @author :Veiking
 * @version :2020年10月1日 
 * 说明 :冒泡排序算法
 */
public class BubbleSort {
    /**
     * 冒泡排序（原始版）
     * @param arrays
     * @return
     */
    public static int[] sort(int[] arrays) {
        int temp;
        int index;
        int size = arrays.length;
        // 每一轮的冒泡会将最大的元素浮至最后，结下对剩余的重复操作，直至处理完毕
        for (int times = 1; times < size - 1; times++) {
            // 在剩余的待排数据中，相邻元素，大的后浮
            for (index = 0; index <= size - 1 - times; index++) {
                if (arrays[index] > arrays[index + 1]) {
                    temp = arrays[index];
                    arrays[index] = arrays[index + 1];
                    arrays[index + 1] = temp;
                }
            }
            // System.out.println("第" + times + "次排序操作结果：" + Arrays.toString(arrays));
        }
        return arrays;
    }

    // 执行
    public static void main(String[] args) {
        int[] input = new int[] { 3, 7, 2, 6, 1, 5, 4 };
        System.out.println("样本初始样本数据：" + Arrays.toString(input));
        int[] output = BubbleSort.sort(input);
        System.out.println("冒泡排序结果数据：" + Arrays.toString(output));
    }
}

  从代码运行的时候，我们可以看到：

样本初始样本数据：[3, 7, 2, 6, 1, 5, 4]
第1次冒泡操作结果：[3, 2, 6, 1, 5, 4, 7]
第2次冒泡操作结果：[2, 3, 1, 5, 4, 6, 7]
第3次冒泡操作结果：[2, 1, 3, 4, 5, 6, 7]
第4次冒泡操作结果：[1, 2, 3, 4, 5, 6, 7]
第5次冒泡操作结果：[1, 2, 3, 4, 5, 6, 7]
冒泡排序结果数据：[1, 2, 3, 4, 5, 6, 7]

  其实在执行第4次操作的时候，已经完成了排序，如果数据样本刚开始就是正序的，岂不是要空跑很多轮！于是，我们一般是在做了交换操作之后，做个判断标识，例：

    /**
     * 冒泡排序（加标识版）
     * @param arrays
     * @return
     */
    public static int[] sort_1(int[] arrays) {
        int temp;
        int index;
        int size = arrays.length;
        // 每一轮的冒泡会将最大的元素浮至最后，结下对剩余的重复操作，直至处理完毕
        for(int times = 1; times < size-1; times++) {
            boolean flag = true;
            //在剩余的待排数据中，相邻元素，大的后浮
            for(index = 0; index <= size-1-times; index++) {
                if(arrays[index]>arrays[index+1]){
                    temp = arrays[index];
                    arrays[index] = arrays[index+1];
                    arrays[index+1] = temp;
                    flag = false;
                }
            }
            if(flag) {
                break;
            }
            // System.out.println("第"+times+"次冒泡操作结果："+Arrays.toString(arrays));
        }
        return arrays;
    }

  我们在一次遍历完成后，看他有没有“冒泡”交换，如果没有，可判定这剩下的数据，是已经符合排序规则了的，那就不用管了，直接跳出。
  还有，看到有些朋友玩了一个招式，说咱们冒泡，获取大或取小，一般都是一头开始，单向冒；那我给他升级下，从数据的两头分别开始，正向取大、反向取小，这样一次可以就得到两个最终值(最大者和最小者) ，看样子还可以节省一半时间，大致程序如下：

    /**
     * 冒泡排序（双开版）
     * @param arrays
     * @return
     */
    public static int[] sort_2(int[] arrays) {
        int head = 0;
        int tail = arrays.length - 1; // 设置变量的初始值
        int temp, index;

        while (head < tail) {
            boolean flag = true;
            // 从前往后，正向冒泡,冒出最大
            for (index = head; index < tail; ++index)
                if (arrays[index] > arrays[index + 1]) {
                    temp = arrays[index];
                    arrays[index] = arrays[index + 1];
                    arrays[index + 1] = temp;
                    flag = false;
                }
            // System.out.println("正向冒泡操作结果："+Arrays.toString(arrays));
            tail--; // 修改tail值, 前移一位
            // 从后往前，反向冒泡,冒出最小
            for (index = tail; index > head; --index)
                if (arrays[index] < arrays[index - 1]) {
                    temp = arrays[index];
                    arrays[index] = arrays[index - 1];
                    arrays[index - 1] = temp;
                    flag = false;
                }
            // System.out.println("反向冒泡操作结果："+Arrays.toString(arrays));
            head++; // 修改head值,后移一位
            if (flag) {
                break;
            }
        }
        return arrays;
    }

  其实细看细想，这一前一后双开，跟从一头单开，基本是没有区别的，因为冒泡算法的基本操作原理就在那里，你从前往后，从后往前，还是都要这么轮一遍，1×1是等于2×1/2的，这从时间复杂度上来说，并没有达成什么优化效果，反倒造成了思路复杂、代码臃肿。
  我们在刚开始学习算法的时候，可能经常会遇到这样的情况，尤其是一些东西搞得还不是太清楚的时候，做性能优化，是力不从心的，结果很有可能是走了弯路，弄巧成拙。不过对于我们学习者来说，怎么折腾都不为过，都是值得肯定的，学的时候不折腾，怎么可能搞清楚！

  冒泡算法的基本性能，归纳如下图：

1、 时间复杂度

  我们可以看到，如果数据文件的初始状态是正序的，冒泡这么比较着冒一遍，就可以排序完成。这时候，数据元素的比较次数和交换次数，分别是n-1和0，这时候冒泡排序是最爽的，也就是说冒泡排序最好时间复杂度为O(n)；
  事实上哪那么多好事儿，排序还是要排的，你要正着排，偏来一个反序的，这就热闹了。冒泡排序的特点决定，当遇到反序的数据样本时，一遍又一遍，从头到尾要一直比一直换，这时候数据元素的比较次数和交换次数，分别是O(n2)和O(n2)，都是O(n2)，这时候冒泡排序是最颓的，我们说冒泡排序最坏时间复杂度为O(n2)；此外，冒泡排序的平均时间复杂度为O(n2)。
  总结一下，冒泡排序最好时间复杂度为O(n)，最坏时间复杂度为O(n2)，平均时间复杂度为最坏时间复杂度为O(n2)。当数据越接近正序时，冒泡排序性能越好；当数据越接近反序时，冒泡排序性能越差。

2、空间复杂度

  冒泡排序的空间复杂度是O（1），因为只定义了一个辅助交换的变量，与n的大小无关，所以空间复杂度为O（1）。

3、稳定性

  我们通过图解和程序可以看出，在冒泡排序中，当对比出现等值的元素，是没必要互相动他们的，也就是说，即使经过排序，这些数据元素的相对顺序也是不受影响的，所以冒泡排序属于稳定的排序算法。