冒泡排序

1. 思想

冒泡排序，人如其名，排序过程就是一个不断冒泡的过程。
在冒泡过程中，值较大的元素下沉，值较小的元素上浮，逐渐形成有序。

若序列 A A A 中有 n n n 个元素，通常需要进行 n − 1 n-1 n−1 轮。
第 1 轮，针对 A [ 1 ] A[1] A[1] 至 A [ n ] A[n] A[n] 元素进行排序；
第 2 轮，针对 A [ 1 ] A[1] A[1] 至 A [ n − 1 ] A[n-1] A[n−1] 元素进行排序；
……；
第 n − 1 n-1 n−1 轮，针对 A [ 1 ] A[1] A[1] 至 A [ 2 ] A[2] A[2] 元素进行排序。

每一轮进行的过程：比较相邻的两个元素，如果不满足相对顺序，则进行交换；否则，不进行操作。
直到这一轮中所有的元素和相邻元素的相对顺序正确。

2. 算法

在这里插入图片描述

3. 代码

public class BubbleSort
{ 
    /** * 交换数组中的两个元素 * * @param array 一维数组 * @param firstIndex 待交换的第一个元素下标 * @param secondIndex 待交换的第二个元素下标 */
    public static void swap(int[] array, int firstIndex, int secondIndex)
    { 
        int buffer = array[firstIndex];
        array[firstIndex] = array[secondIndex];
        array[secondIndex] = buffer;
    }
    /** * 冒泡排序 * * @param array 待排序的数组，也作为排序后的数组 */
    public static void bubbleSort(int[] array)
    { 
        for (int i = 0; i < array.length - 1; ++i)
        { 
            for (int j = 0; j < array.length - 1 - i; ++j)
            { 
                if (array[j] > array[j + 1])
                { 
                    swap(array, j, j + 1);
                }
            }
            System.out.println("第 " + (i + 1) + " 轮：" + Arrays.toString(array));
        }
    }
}

4. 结果

在这里插入图片描述

结论：数组中的元素按照非递减顺序存储，排序结果正确。

5. 疑问

观察输出结果可以发现：

第 6 轮排序的结果已经是最终的结果，第 7 ~ 9 轮排序无意义（浪费时间）。

是否可以改进上面的算法，使得在中间某一轮达到最终排序结果的时候，停止冒泡算法呢？
答案是：可以！

6. 改进

观察第 6 轮和第 7 轮冒泡排序，发现第 7 轮和第 6 轮排序后的结果完全一致。也即是说，第 7 轮冒泡排序没有交换任意两个元素。那么这一条件，可以作为冒泡排序算法的终止条件。

在这里插入图片描述

7. 更新

public class BubbleSort
{ 
    /** * 交换数组中的两个元素 * * @param array 一维数组 * @param firstIndex 待交换的第一个元素下标 * @param secondIndex 待交换的第二个元素下标 */
    public static void swap(int[] array, int firstIndex, int secondIndex)
    { 
        int buffer = array[firstIndex];
        array[firstIndex] = array[secondIndex];
        array[secondIndex] = buffer;
    }
    /** * 冒泡排序改进版 * * @param array 待排序数组，也作为排序后的数组 */
    public static void bubbleSortAdvanced(int[] array)
    { 
        boolean swapFlag = true;
        for (int i = 0; swapFlag && i < array.length - 1; ++i)
        { 
            swapFlag = false;
            for (int j = 0; j < array.length - 1 - i; ++j)
            { 
                if (array[j] > array[j + 1])
                { 
                    swap(array, j, j + 1);
                    if (!swapFlag)
                    { 
                        swapFlag = true;
                    }
                }
            }
            System.out.println("第 " + (i + 1) + " 轮：" + Arrays.toString(array));
        }
    }
}

结论：数组中的元素按照非递减顺序存储，排序结果正确。

8. 比较

在这里插入图片描述

9. 源码

package louis;
import java.util.Arrays;
public class BubbleSort
{ 
    /** * 交换数组中的两个元素 * * @param array 一维数组 * @param firstIndex 待交换的第一个元素下标 * @param secondIndex 待交换的第二个元素下标 */
    public static void swap(int[] array, int firstIndex, int secondIndex)
    { 
        int buffer = array[firstIndex];
        array[firstIndex] = array[secondIndex];
        array[secondIndex] = buffer;
    }
    /** * 冒泡排序 * * @param array 待排序的数组，也作为排序后的数组 */
    public static void bubbleSort(int[] array)
    { 
        for (int i = 0; i < array.length - 1; ++i)
        { 
            for (int j = 0; j < array.length - 1 - i; ++j)
            { 
                if (array[j] > array[j + 1])
                { 
                    swap(array, j, j + 1);
                }
            }
            System.out.println("第 " + (i + 1) + " 轮：" + Arrays.toString(array));
        }
    }
    /** * 冒泡排序改进版 * * @param array 待排序数组，也作为排序后的数组 */
    public static void bubbleSortAdvanced(int[] array)
    { 
        boolean swapFlag = true;
        for (int i = 0; swapFlag && i < array.length - 1; ++i)
        { 
            swapFlag = false;
            for (int j = 0; j < array.length - 1 - i; ++j)
            { 
                if (array[j] > array[j + 1])
                { 
                    swap(array, j, j + 1);
                    if (!swapFlag)
                    { 
                        swapFlag = true;
                    }
                }
            }
            System.out.println("第 " + (i + 1) + " 轮：" + Arrays.toString(array));
        }
    }
    /** * main 函数，进行测试。 * * @param args 系统输入的参数 */
    public static void main(String[] args)
    { 
        int[] array = new int[]{ 43, 32, 76, -98, 0, 64, 33, -21, 32, 99};
        bubbleSort(array);
        System.out.println("Bubble Sort 最终结果：" + Arrays.toString(array));
        array = new int[]{ 43, 32, 76, -98, 0, 64, 33, -21, 32, 99};
        bubbleSortAdvanced(array);
        System.out.println("Bubble Sort Advanced 最终结果：" + Arrays.toString(array));
    }
}