===============
== 大程熙 ==
===============
一个小学生

算法之冒泡排序学习

冒泡排序算法重新学习。

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

  • 冒泡排序
  • 快速排序

冒泡排序算法

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

冒泡排序代码示例

/**
 * 冒泡排序
 */
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版)》