用Java實現冒泡排序

排序演算法的數量相當多，其中許多演算法都非常具體，是為了解決一小部分問題並處理特定類型的資料而開發的。但在所有這些多樣性中，最簡單的演算法當之無愧的是冒泡排序，它可以用任何程式語言實作。儘管它很簡單，但它是許多相當複雜的演算法的基礎。另一個同樣重要的優點是它的簡單性，因此可以立即記住並實施它，而無需您面前有任何其他文獻。在 Java 中實作冒泡排序 - 1

介紹

整個現代互聯網由資料庫中收集的大量不同類型的資料結構組成。它們儲存各種信息，從用戶的個人數據到高度智慧自動化系統的語義核心。不用說，資料排序在如此海量的結構化資訊中發揮著極其重要的作用。排序可能是在資料庫中搜尋任何資訊之前的強制性步驟，排序演算法的知識在程式設計中起著非常重要的作用。

透過機器眼和人眼分類

假設您需要對 5 列不同高度的升序進行排序。這些列可以表示任何類型的信息（股票價格、通訊通道頻寬等），您可以呈現此任務的一些您自己的版本以使其更加清晰。好吧，舉個例子，我們將按照身高對復仇者聯盟進行排序：

與電腦程式不同，排序對您來說並不困難，因為您可以看到全局，並且可以立即找出需要將哪個英雄移動到哪裡才能成功完成按高度排序。您可能已經猜到，要按升序對這個資料結構進行排序，只需交換綠巨人和鋼鐵人的位置即可：

完畢！

這樣就可以成功完成排序了。然而，計算機與你不同，~~它有些愚蠢~~，它不能將整個資料結構視為一個整體。它的控製程式一次只能比較兩個值。為了解決這個問題，她必須將兩個數字放入記憶體中並對它們執行比較操作，然後轉向另一對數字，依此類推，直到分析完所有資料。因此，任何排序演算法都可以非常簡化為三個步驟的形式：

比較兩個元素；
交換或複製其中之一；
轉到下一個元素；

不同的演算法可以以不同的方式執行這些操作，但我們將繼續考慮冒泡排序的工作原理。

冒泡排序演算法

冒泡排序被認為是最簡單的，但在描述這個演算法之前，讓我們想像一下，如果你可以像一台機器一樣，在一段時間內只比較兩個英雄，你將如何按身高對復仇者進行排序。最有可能的是，您會按照以下方式（最優化）進行操作：

您移動到數組的零元素（黑寡婦）；
將零元素（黑寡婦）與第一個元素（綠巨人）進行比較；
如果位置 0 的元素較高，則交換它們；
否則，如果位置 0 處的元素較小，則將它們保留在原來的位置；
移動到右側的位置並重複比較（將綠巨人與船長進行比較）

當你用這樣的演算法一次遍歷完整個列表後，排序並不能完全完成。但另一方面，清單中最大的元素將被移動到最右邊的位置。這種情況總是會發生，因為一旦你找到最大的元素，你就會不斷地改變位置，直到你把它移到最後。也就是說，一旦程式在陣列中「找到」綠巨人，它就會將他進一步移動到清單的最後：

這就是為什麼該演算法被稱為冒泡排序，因為其操作的結果是，列表中最大的元素將位於數組的最頂部，而所有較小的元素將向左移動一位：

要完成排序，您需要返回數組的開頭並再次重複上述五個步驟，再次從左到右移動，根據需要比較和移動元素。但這次你需要在陣列結尾前一個元素停止演算法，因為我們已經知道最大的元素（Hulk）絕對在最右邊的位置：

所以程式必須有兩個循環。為了更清楚起見，在我們繼續查看程式碼之前，您可以透過此連結查看冒泡排序如何運作的視覺化：視覺化冒泡排序的工作原理

Java冒泡排序的實現

為了示範 Java 中排序的工作原理，以下是程式碼：

建立一個包含 5 個元素的陣列；
將復仇者聯盟上傳到其中；
顯示數組的內容；
實現冒泡排序；
重新顯示排序後的陣列。

您可以查看下面的程式碼，甚至可以將其下載到您最喜歡的~~IntelliJ~~ IDE 中。下面將對其進行分析：

class ArrayBubble{
    private long[] a;   // array reference
    private int elems;  //number of elements in the array

    public ArrayBubble(int max){    //class constructor
        a = new long[max];          //create an array with size max
        elems = 0;                  //when created, the array contains 0 elements
    }

    public void into(long value){   // method for inserting an element into an array
        a[elems] = value;           //insert value into array a
        elems++;                    //array size increases
    }

    public void printer(){          // method for outputting an array to the console
        for (int i = 0; i < elems; i++){    //for each element in the array
            System.out.print(a[i] + " ");   // output to console
            System.out.println("");         //a new line
        }
        System.out.println("----End array output----");
    }

    private void toSwap(int first, int second){ //method swaps a pair of array numbers
        long dummy = a[first];      // put the first element into a temporary variable
        a[first] = a[second];       // put the second element in place of the first
        a[second] = dummy;          //instead of the second element, write the first from temporary memory
    }

    public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
        for (int out = elems - 1; out >= 1; out--){  //Outer loop
            for (int in = 0; in < out; in++){       //Inner loop
                if(a[in] > a[in + 1])               //If the order of the elements is wrong
                    toSwap(in, in + 1);             // call the swapping method
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayBubble array = new ArrayBubble(5); //Create array array with 5 elements

        array.into(163);       //fill the array
        array.into(300);
        array.into(184);
        array.into(191);
        array.into(174);

        array.printer();            //display elements before sorting
        array.bubbleSorter();       //ИСПОЛЬЗУЕМ ПУЗЫРЬКОВУЮ СОРТИРОВКУ
        array.printer();            // print the sorted list again
    }
}

儘管程式碼中有詳細的註釋，我們還是提供了程式中提供的一些方法的描述。程式中執行主要工作的關鍵方法都寫在 ArrayBubble 類別中。此類別包含一個建構函式和幾個方法：

into– 將元素插入陣列的方法；
printer– 逐行顯示陣列內容；
toSwap– 如有必要，重新排列元素。為此，使用臨時變量dummy，將第一個數字的值寫入其中，並在第一個數字的位置寫入第二個數字的值。然後臨時變數的內容被寫入第二個數字。這是交換兩個元素的標準技術；

最後是主要方法：

bubbleSorter– 它的主要工作是對數組中儲存的資料進行排序，我們將再次單獨介紹：

public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
    for (int out = elems - 1; out >= 1; out--){  //Outer loop
        for (int in = 0; in < out; in++){       //Inner loop
            if(a[in] > a[in + 1])               //If the order of the elements is wrong
                toSwap(in, in + 1);             // call the swapping method
        }
    }
}

這裡你應該要注意兩個計數器：externalout和internal in。 外部計數器out從數組末尾開始枚舉值，並在每次新遍歷時逐漸減一。out每次新傳遞時，變數都會進一步向左移動，以免影響已排序到陣列右側的值。內部計數器in從數組的開頭開始列舉值，並在每次新傳遞時逐漸加一。增加in一直發生，直到達到out（當前通道中最後一個分析的元素）。內循環in比較兩個相鄰單元格in和in+1。如果in比中儲存的數字更大in+1，則呼叫該方法toSwap，該方法交換這兩個數字的位置。

結論

冒泡排序演算法是最慢的演算法之一。如果陣列由 N 個元素組成，則第一遍將執行 N-1 次比較，第二遍將執行 N-2 次比較，然後是 N-3 次比較，依此類推。也就是說，總遍歷次數為： (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 因此，在排序時，演算法執行大約0.5 x(N ^2) 次比較。當 N = 5 時，比較次數約為 10 次，當 N = 10 時，比較次數將增加到 45 次。因此，隨著元素數量的增加，排序的複雜度顯著增加：

演算法的速度不僅受到傳遞次數的影響，也受到需要進行的排列的數量的影響。對於隨機數據，排列次數平均值為 (N^2) / 4，約為遍數的一半。然而，在最壞的情況下，排列的數量也可以是 N^2 / 2 - 如果資料最初以相反的順序排序，就會發生這種情況。儘管這是一種相當緩慢的排序演算法，但了解和理解它的工作原理非常重要，並且如前所述，它是更複雜演算法的基礎。天哪！

留言

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION