:-: 14.1 冒泡排序 * * * * * **基本概念：** 它是一种简单却又复杂排序（代码，理解简单，运算相比其他较复杂），它的工作原理是从无序序列头部开始，进行两两比较，根据大小交换位置，直到最后将最大（小）的数据元素交换到了无序队列的队尾，从而成为有序序列的一部分；下一次继续这个过程，直到所有数据元素都排好序。 冒泡排序算法的核心在于每次通过两两比较交换位置，选出剩余无序序列里最大（小）的数据元素放到队尾。 **算法的运作：** 1、比较相邻的元素。如果第一个比第二个大（小），就交换他们两个。 2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对（未经过检测排好序的数列）。这步做完后，最后的元素会是最大（小）的数。 3、针对除了最后已经排好序的元素的元素重复以上的步骤，。 4、持续每次对越来越少的元素（无序元素）重复上面的步骤，直到没有任何一对数字需要比较，则序列最终有序。 **图片示例：** :-:  :-:  :-:  **代码实现：** 第一种方式：从小到大排序，寻找其中最小的元素排在头部。 ~~~ public void bubbleSort(int sums[]) { int sign = 0; for (int i = 0; i < sums.length; i++) { for (int j = i + 1; j < sums.length; j++) { if (sums[i] > sums[j]) { sign = sums[i]; sums[i] = sums[j]; sums[j] = sign; } } } } ~~~ 第二种方式：从小到大排序，寻找其中最大的元素排在尾部。 ~~~ public void bubbleSort(int sums[]) { int sign = 0; for (int i = 0; i < sums.length - 1; i++) { for (int j = 0; j < sums.length - 1 - i; j++) { if (sums[j] > sums[j + 1]) { sign = sums[j]; sums[j] = sums[j + 1]; sums[j + 1] = sign; } } } } ~~~ 第三种方式：从小到大排序，我们分析一下上面两种排序算法，我们会发现，如果我们输入[5,6,7,8],它还是会经过两次for循环来排序，但是我们的原数组这已经顺序已经排好了呀。我们怎么避免这种情况呢？我们可以做个标记，来判断当前的数组有无需要交换的元素，这样最优的情况下时间复杂度会降到O(n)。 ~~~ public void bubbleSort(int sums[]) { int sign = 0; boolean bubble = false; int length = sums.length; do { bubble = false; length -= 1; for (int i = 0; i < length; i++) { if (sums[i] > sums[i + 1]) { sign = sums[i]; sums[i] = sums[i + 1]; sums[i + 1] = sign; bubble = true; } } } while (bubble); } ~~~ **复杂度分析：** 时间复杂度：平均：O(n^2)、最坏：O(n^2)、最优：O(n)。 空间复杂度：O(1)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。** **本文主要参考以下文章：** [维基百科——冒泡排序](https://zh.wikipedia.org/wiki/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F) [冒泡排序详解（示例图片来源）](https://blog.csdn.net/guoweimelon/article/details/50902597) [JS中常见排序算法（示例图片来源）](https://github.com/Sir814/Sort/blob/master/01.%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F.gif)