原理：每次比较两个相邻的元素，将较大的元素交换至右端。

思路：每次冒泡排序操作都会将相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足，就交换这两个相邻元素的次序，一次冒泡至少让一个元素移动到它应该排列的位置，重复N次，就完成了冒泡排序。

具体如何移动呢？举一个栗子：

有8个数组成一个无序数列：5，8，6，3，9，2，1，7，希望从小到大排序。

首先让和比较，发现和要小，因此元素位置不变。
，，6，3，9，2，1，7

接下来让和比较，发现和要大，所以和交换位置。
5，，，3，9，2，1，7

继续让和比较，发现和要大，所以和交换位置。
5，6，，，9，2，1，7

继续让和比较，发现和要小，所以元素位置不变。
5，6，3，，，2，1，7

接下来让和比较，发现和要大，所以和交换位置。
5，6，3，8，，，1，7

接下来让和比较，发现和要大，所以和交换位置。
5，6，3，8，2，，，7

这样第一轮比较，就找到了元素作为最大元素，排序在最右侧。
5，6，3，8，2，1，7，

下面进行第二轮排序

首先让和比较，发现和要小，因此元素位置不变。
，，3，8，2，1，7，9

接下来让和比较，发现和要大，所以和交换位置。
5，，，8，2，1，7，9

继续让和比较，发现比要小，因此元素位置不变。
5，3，，，2，1，7，9

接下来让和比较，发现和要大，所以和交换位置。
5，3，6，2，，1，7，9

接下来让和比较，发现和要大，所以和交换位置。
5，3，6，2，，，7，9

继续让和比较，发现和要大，所以和交换位置。
5，3，6，2，1，，，9

接下来如同上进行八轮比较得到；
1，2，3，5，6，7，，

第二轮比较结束后，得到了两个有序的最大元素 ,：

原始的冒泡排序是稳定排序。由于该排序算法的每一轮要遍历所有元素，轮转的次数和元素数量相当，所以时间复杂度是O（N^2） 。

下面呈上代码：

private static void sort1(int array[]) {
        int tmp = 0;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                }
            }
        }
    }

原始的冒泡排序有哪些优化点呢？

让我们回顾一下刚才描述的排序细节，仍然以5，8，6，3，9，2，1，7这个数列为例，当排序算法分别执行到第六、第七、第八轮的时候，数列状态如下：

第六轮比较
1，2，3，5，6，7，8，9

第七轮比较
1，2，3，5，6，7，8，9

第八轮比较
1，2，3，5，6，7，8，9

很明显可以看出，自从经过第六轮排序，整个数列已然是有序的了。可是我们的排序算法仍然“兢兢业业”地继续执行第七轮、第八轮。

这种情况下，如果我们能判断出数列已经有序，并且做出标记，剩下的几轮排序就可以不必执行，提早结束工作。

冒泡排序优化版

 /**
     * 这一版代码做了小小的改动，利用布尔变量isSorted作为标记。如果在本轮排序中，元素有交换，则说明数列无序；如果没有元素交换，说明数列已然有序，直接跳出大循环。
     * @param array
     */
    private static void sort2(int array[]) {
        int tmp = 0;
        for (int i = 0; i < array.length; i++) {
            boolean isSorted = true;                  //有序标记，每一轮的初始是true
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    isSorted = false;                //有元素交换，所以不是有序，标记变为false
                }
            }
            if (isSorted) {
                break;
            }
        }
    }

这只是冒泡排序优化的第一步，下面还可以进一步优化提升性能！

为了说明问题，咱们这次找一个新的数列：
3，4，2，1，5，6，7，8

这个数列的特点是前半部分（3，4，2，1）无序，后半部分（5，6，7，8）升序，并且后半部分的元素已经是数列最大值。

这个问题的关键点在哪里呢？关键在于对数列有序区的界定。

按照现有的逻辑，有序区的长度和排序的轮数是相等的。比如第一轮排序过后的有序区长度是1，第二轮排序过后的有序区长度是2 ......

实际上，数列真正的有序区可能会大于这个长度，比如例子中仅仅第二轮，后面5个元素实际都已经属于有序区。因此后面的许多次元素比较是没有意义的。

如何避免这种情况呢？我们可以在每一轮排序的最后，记录下最后一次元素交换的位置，那个位置也就是无序数列的边界，再往后就是有序区了。

冒泡排序再次优化

 /**
     * 这一版代码中，sortBorder就是无序数列的边界。每一轮排序过程中，sortBorder之后的元素就完全不需要比较了，肯定是有序的。
     * @param array
     */
    private static void sort3(int array[]) {
        int tmp = 0;
        int lastExchangeIndex = 0;                        //记录最后一次交换的位置
        int sortBorder = array.length - 1;                //无序数列的边界，每次比较只需要比到这里为止
        for (int i = 0; i < array.length; i++) {
            boolean isSorted = true;                      //有序标记，每一轮的初始是true
            for (int j = 0; j < sortBorder; j++) {
                if (array[j] > array[j + 1]) {
                    tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    isSorted = false;                     //有元素交换，所以不是有序，标记变为false
                    lastExchangeIndex = j;                //把无序数列的边界更新为最后一次交换元素的位置
                }
            }
            sortBorder = lastExchangeIndex;
            if (isSorted) {
                break;
            }
        }
    }

原文地址