排序算法 - 气泡排序的原理和代码实现

冒泡排序（BubbleSort）是一种基础的交换排序，可以将无序数组按规则（规则：例如从小到大）排序。

算法原理

冒泡排序实例：从小到大排序

数组中所有相邻的元素两两比较，当满足规则时交换两个元素的位置，所有元素比较完后，本轮结束，数据中有多少元素，执行多少轮比较。
第一轮结束后，最满足规则的元素会在数组的顶端，继续下一轮；
第二轮结束后，次满足规则的元素会在数组的次顶端，继续下一轮；
...
最后一轮结束后，数组完成排序。

代码实现

使用Java实现简单的冒泡排序

	public static void main(String[] args) {
        int[] array = new int[]{5, 8, 6, 3, 9, 2, 1, 7, 10};
        sortSimple(array);
    }
	/**
     * 最简单的冒泡排序
     *
     * @param array
     */
    public static void sortSimple(int[] array) {
        System.out.println("排序前：" + Arrays.toString(array));
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                	// 交换两数位置
                    swap(array, j, j + 1);
                }
                System.out.println("第：" + (i + 1) + "轮第" + (j + 1) + "次" + Arrays.toString(array));
            }
        }
        System.out.println("排序后：" + Arrays.toString(array));
    }
    
    /**
     * 交换数组中两个元素的位置
     *
     * @param array 数组
     * @param i     元素i
     * @param j     元素j
     */
    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

性能优化

排序中发现已完成排序，直接终止

如果一轮排序中没有任何元素交换顺序，说明数组已经有序，直接终止排序。

在sortSimple中，可以发现第7、8轮排序中没有任何元素交换顺序，所以我们可以在第7轮结束后直接终止后续排序。

/**
     * 冒泡排序优化 - 如果一轮排序中没有任何元素交换顺序，说明数组已经有序，直接终止排序
     * <p>
     * 在sortSimple中，可以发现第7、8轮排序中没有任何元素交换顺序，所以我们可以在第7轮结束后直接终止后续排序。
     *
     * @param array
     */
    public static void sortSimple1(int[] array) {
        System.out.println("排序前：" + Arrays.toString(array));
        for (int i = 0; i < array.length; i++) {
            boolean isSorted = true;
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    isSorted = false;
                }
                System.out.println("第：" + (i + 1) + "轮第" + (j + 1) + "次" + Arrays.toString(array));
            }
            if (isSorted) {
                break;
            }
        }
        System.out.println("排序后：" + Arrays.toString(array));
    }