排序-冒泡排序 - JAVA学习网

https://en.wikipedia.org/wiki/Bubble_sort

原理:从低位到高位的对比排序;通过compare和 swap达到排序的目的
对于冒泡排序由于其并不需要额外的内存空间,只需要原数组就可以达到排序的目的,不需要额外的内存空间,因此属于原地排序
稳定性分析
- 从低位到高位进行对比时,当存在相同数据的情况时,并不会发生交换操作,因此对于排序前和排序后,相同元素的相对位置并不会发生变化,因此属于稳定性排序

　　java代码实现

public interface Sort<T extends Comparable<T>> {
    /**
     * 对数组进行排序
     *
     * @param array
     * @param flag  true 代表的是正序;false代表的是逆序
     */
    void sort(T[] array, boolean flag);
}

public class BubbleSort<T extends Comparable<T>> implements Sort<T> {

    @Override
    public void sort(T[] array, boolean flag) {
        if (array == null || array.length < 2) {
            return;
        }
        int length = array.length;
        //
        // 对于Comparable.compareTo 默认
        // < -1
        // = 0
        // > 1
        // 每一次排序都能保证有一个元素在最终位置
        // i 表示总共要冒泡的次数
        for (int i = 0; i < length - 1; i++) {
            // 限制第一个元素要对比的数量, 由于每执行一次冒泡,都能保证肯定会有一个元素在其最终位置,因此下一次冒泡时就不需要在操作该元素,因此j < length - 1 - i
            /**
             * 假设存在以下元素
             *  5    3   2   1  需要进行升序排序
             *  j
             * 第一次冒泡
             *  5  > 3 ,需要对 5和 3进行交换位置
             *  3   5   2   1
             *      j
             *      5 > 2 , 需要对5 和 2 进行交换位置
             *  3   2   5   1
             *          j
             *          5  > 1 需要对 5 和 1进行交换位置
             *  3   2   1   5
             *              j 此时 j 走到了尽头,代表当前一次冒泡结束; 对于j而言,每次都是指向当前已比较的最大的数;
             *              每一次冒泡都能保证肯定有一个元素在其最终位置上,因此对于下一次的冒泡对比的元素的个数就应该比上一次 - 1
             */
            for (int j = 0; j < length - 1 - i; j++) {
                if ((flag && array[j].compareTo(array[j + 1]) == 1) || (!flag && array[j].compareTo(array[j + 1]) == -1)) {
                    T v = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = v;
                }
            }
        }
    }

    public static void main(String[] args) {
        Integer[] values = new Integer[]{5, 3, 2, 1};
        BubbleSort<Integer> integerBubbleSort = new BubbleSort<>();
        integerBubbleSort.sort(values, true);
        Stream.of(values).forEach(System.out::print);
        System.out.println();
        integerBubbleSort.sort(values, false);
        Stream.of(values).forEach(System.out::print);
    }
}

对于冒泡排序实际就是对当前数组中的全部元素都执行一遍冒泡; 这就是第一层 for循环的含义,要保证全部的元素都经过冒泡处理;对于i的作用实际就是为了控制当前冒泡操作的总次数,并没有指向元素的含义

在执行冒泡操作时主要是执行对比和交换操作,这就是第二层for循环的含义,对于 j < length - 1 - i ;

由于数据对比操作是需要操作相邻的两个元素,因此对于游标而言,并不需要指向最后一个元素,只需要指向最后一个元素的前一个元素即可,因此存在 length-1;
对于 "-i"操作原因在于,每执行一次冒泡操作,保证肯定有一个元素在其高位的最终位置;因此对于下一次冒泡操作,就不需要在操作已经有序的高位列表

对于每一次冒泡操作都是从低位到高位的对比; 都是j 和 j+1 位元素的对比; 对于当前操作的具象表示可以查看维基百科中的动态图片

"未完待续-----剩余使用python+Matplotlib 绘制可视化动画"

https://zhuanlan.zhihu.com/p/38157591

JAVA学习网

分类