算法之冒泡排序学习

2021-02-18 20:30:00

冒泡排序算法重新学习。

交换排序算法有以下几种：

冒泡排序
快速排序

冒泡排序算法

冒泡排序算法描述：比较相邻两个元素大小，如果是反序，就将两个元素进行交换。

冒泡排序代码示例

/**
 * 冒泡排序
 */
public class BubbleSort {

    /**
     * 冒泡排序
     * @param source 待排序数组
     * @param asc 是否升序 true：升序（从小到大）false：降序（从大到小）
     */
    public void bubbleSort(Integer[] source, boolean asc) {

        for (int i = 1; i < source.length; i++) {
            for (int j = 0; j < source.length - i; j++) {
                if (asc ? source[j] > source[j + 1] : source[j] < source[j + 1]) {
                    int temp = source[j];
                    source[j] = source[j + 1];
                    source[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        Integer[] array = new Integer[] {38, 55, 65, 97, 27, 76, 27, 13, 19};
        System.out.println("before: " + Arrays.asList(array));
        new BubbleSort().bubbleSort(array, true);
        System.out.println("after: " + Arrays.asList(array));
    }
}

算法改进

原始冒泡排序，如果在中间某一趟就已经排序完成了，后续的每一趟比较都不会有任何变化，后面这些都是多余的，可以使用一个标志位来进行控制。如果某一趟没有交换元素，说明已经排好序，下次循环判断标志位就可以直接结束。优化后代码如下：

/**
 * 冒泡排序
 */
public class BubbleSort {

    /**
     * 冒泡排序
     * @param source 待排序数组
     * @param asc 是否升序 true：升序（从小到大）false：降序（从大到小）
     */
    public void bubbleSort(Integer[] source, boolean asc) {
        // 标志位
        boolean exchange = true;
        for (int i = 1; i < source.length && exchange; i++) {
            exchange = false;
            for (int j = 0; j < source.length - i; j++) {
                if (asc ? source[j] > source[j + 1] : source[j] < source[j + 1]) {
                    Integer temp = source[j];
                    source[j] = source[j + 1];
                    source[j + 1] = temp;
                    exchange = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        Integer[] array = new Integer[] {38, 55, 65, 97, 27, 76, 27, 13, 19};
        System.out.println("before: " + Arrays.asList(array));
        new BubbleSort().bubbleSort(array, true);
        System.out.println("after: " + Arrays.asList(array));
    }
}

冒泡排序算法分析

时间复杂度

最好情况，数据已经排好序，只需要一趟扫描，比较n次，没有数据移动，时间复杂度O(n)
最坏情况，数据是随机排列或者反序排列，需要n-1趟扫描，比较和移动次数都是$n^2$，时间复杂度$O(n^2)$

进行冒泡排序的序列，序列越接近有序，效率越高。

空间复杂度

算法中使用一个temp变量占用一个存储单元，用于交换两个元素，空间复杂度为O(1)

算法的稳定性

冒泡排序算法中两两元素之间进行排序，相等记录之间经过排序后，次序保持不变，因此冒泡排序是稳定的。

适用场景

数据规模较小，元素基本有序，可以使用冒泡排序。

需要优化的地方

冒泡排序中，假设元素是按照反序排列，则一趟中，一个元素每次比较都需要交换，元素数据每次都要移动，存在重复移动数据的问题。可以使用快速排序来减少重复数据移动问题。

参考内容

《数据结构（Java版）》