排序算法 - 冒泡排序

基本介绍

• 冒泡排序（Bubble Sorting）的基本思想是：通过对 需要排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的气泡一样逐渐向上冒。
• 每一趟只能确定将一个数归位。即第一趟只能确定将末位上的数归位，第二趟只能将倒数第 2 位上的数归位，依次类推下去。如果有 n 个数进行排序，只需将 n-1 个数归位，也就是要进行 n-1 趟 *** 作。而 “每一趟 ” 都需要从第一位开始进行相邻的两个数的比较，将较大的数放后面，比较完毕之后向后挪一位继续比较下面两个相邻的两个数大小关系，重复此步骤，直到最后一个还没归位的数。
• 优化一：因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。
• 优化二：设置结束边界，记录上一次最后交换的位置，作为下一次循环的结束边界。最后一次比较说明在那之后的元素都已经排好序，无需再比较，可以避免一些无意义的比较。

冒泡过程的例子（图解）

普通的冒泡排序

/**
 * 冒泡法排序
 * @param array 数组
 */
public static void bubbleSort(int[] array) {
    // 临时变量
    int temp;

    // 控制比较轮次，一共 n-1 趟
    for (int i = 0; i < array.length - 1; i++) {
        // 上次遍历之后倒数第 i 位开始 已经是有序的了，所以这次遍历的范围是 [0,array.length - 1 - i)
        for (int j = 0; j < array.length - 1 - i; j++) {
            // 如果前面的数比后面的数大，则交换
            if (array[j] > array[j + 1]) {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }

}

优化一：设置交换标志

冒泡法排序优化，加上flag判断是否进行了交换,没有交换就可以提前结束了。

/**
 * 优化一：设置标志位
 * 冒泡法排序优化,加上flag判断是否进行了交换,没有交换就可以提前结束了。
 * @param array 数组
 */
public static void bubbleSortFlag(int[] array) {
    // 临时变量
    int temp;

    // 控制比较轮次，一共 n-1 趟
    for (int i = 0; i < array.length - 1; i++) {

        // 标识变量，表示是否进行过交换
        boolean flag = false;

        // 上次遍历之后倒数第 i 位开始 已经是有序的了，所以这次遍历的范围是 [0,array.length - 1 - i)
        for (int j = 0; j < array.length - 1 - i; j++) {
            // 如果前面的数比后面的数大，则交换
            if (array[j] > array[j + 1]) {
                flag = true; // 有元素交换，所以不是有序
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }

        // 说明在一趟排序中一次都没有进行过交换
        if (!flag) {
            break;
        }

    }
}

优化二：设置结束边界

记录上一次最后交换的位置，作为下一次循环的结束边界。最后一次比较说明在那之后的元素都已经排好序，无需再比较，可以避免一些无意义的比较。

/**
 * 优化二：设置结束边界
 * 记录上一次最后交换的位置，作为下一次循环的结束边界。
 * 最后一次比较说明在那之后的元素都已经排好序，无需再比较，可以避免一些无意义的比较。
 * @param array array
 */
public static void bubbleSort2(int[] array) {

    if (array == null || array.length < 2) {
        return ;
    }

    // 临时变量
    int temp;
    // 记录最后一次交换的位置
    int lastExchangeIndex = 0;
    // 记录里层下一次循环的终止位置
    int sortBorder = array.length - 1;

    for (int i = 0; i < array.length - 1; i++) {
        // 标识变量，表示是否进行过交换
        boolean flag  = false;
        for (int j = 0; j < sortBorder; j++) {
            if (array[j] > array[j + 1]) {
                flag  = true; // 有元素交换，所以不是有序
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                lastExchangeIndex = j;
            }
        }
        sortBorder = lastExchangeIndex;
        // 说明在一趟排序中一次都没有进行过交换
        if(!flag) {
            break;
        }
    }
}

🤔