算法思路

基本思路

假设按照从小到大排列，总共有n个元素

• 从第一个元素开始至第n-1个元素，依次比较当前元素与它后面相邻元素的大小，如果前面一个比后面一个大，交换两个元素的位置。第一遍处理之后，最后一个元素就是当前循环中最大的一个。
• 重复上面的步骤，第二遍处理第一至第n-2个元素，第三遍处理第一至第n-3个元素……直到仅剩一个元素。

改进后的思路

上面的基本思路中需要进行n-1轮的比较。但是存在一种可能，在其中的某一轮之后，该数组就已经是有序的了，也就意味着后面就不需要再进行额外的比较和交换。可以设置一个标志位，用来表示当前这一轮是否存在元素交换，如果没有的话，就结束整个排序过程

性能

时间复杂度：最好的情况O(n),最差的情况O(n²)， 平均O(n²)

空间复杂度：O(1)

示例代码

未改进的冒泡算法。更多详情可点击链接参考示例代码

private static int[] bubbleSort(int[] unsortedArray) {
    int temp;
    for (int round = 0; round < unsortedArray.length - 1; round ++) {
        // Should have N - 1 rounds

        for (int j = 0; j < unsortedArray.length - 1 - round; j ++) {
            if (unsortedArray[j] > unsortedArray[j + 1]) {
                temp = unsortedArray[j];
                unsortedArray[j] = unsortedArray[j + 1];
                unsortedArray[j + 1] = temp;
            }
        }
    }

    return unsortedArray;
}

用测试用例，有如下的输出。进行了10轮比较，即使后面几轮数组的顺序没有任何的改变

Before sort: 1, 2, 9, 6, 0, 4, 8, 5, 7, 3
After round 1: 1, 2, 6, 0, 4, 8, 5, 7, 3, 9
After round 2: 1, 2, 0, 4, 6, 5, 7, 3, 8, 9
After round 3: 1, 0, 2, 4, 5, 6, 3, 7, 8, 9
After round 4: 0, 1, 2, 4, 5, 3, 6, 7, 8, 9
After round 5: 0, 1, 2, 4, 3, 5, 6, 7, 8, 9
After round 6: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
After round 7: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
After round 8: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
After round 9: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
After sort: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

改进后的示例代码。更多详情可点击链接参考示例代码

private static int[] bubbleSortWithFlag(int[] unsortedArray) {
    int temp;
    boolean swapFlag;
    for (int round = 0; round < unsortedArray.length - 1; round ++) {
        // Should have at least N - 1 rounds

        swapFlag = false;
        for (int j = 0; j < unsortedArray.length - 1 - round; j ++) {
            if (unsortedArray[j] > unsortedArray[j + 1]) {
                temp = unsortedArray[j];
                unsortedArray[j] = unsortedArray[j + 1];
                unsortedArray[j + 1] = temp;

                swapFlag = true;
            }
        }

        if (!swapFlag) {
            // End the process if there is no swap happens
            break;
        }
    }

    return unsortedArray;
}    

用测试用例有如下的输出，可以看到仅仅进行了6轮

Before sort: 1, 2, 9, 6, 0, 4, 8, 5, 7, 3
After round 1: 1, 2, 6, 0, 4, 8, 5, 7, 3, 9
After round 2: 1, 2, 0, 4, 6, 5, 7, 3, 8, 9
After round 3: 1, 0, 2, 4, 5, 6, 3, 7, 8, 9
After round 4: 0, 1, 2, 4, 5, 3, 6, 7, 8, 9
After round 5: 0, 1, 2, 4, 3, 5, 6, 7, 8, 9
After round 6: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
After sort: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9