排序-冒泡排序-有解無憂

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

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/97441.html

標籤：Java

上一篇：關于image中的圖片編輯

下一篇：資料集中欄位型別的區別