Java 資料結構 - 氣泡排序

排序是指以特定格式排列資料。排序演算法指定以特定順序排列資料的方式。最常見的順序是數值順序或字典順序。

排序的重要性在於，如果資料以排序方式儲存，則資料搜尋可以被最佳化到非常高的水平。排序還用於以更易讀的格式表示資料。以下是現實生活中排序的一些示例。

• 電話簿 - 電話簿按姓名對人員的電話號碼進行排序儲存，以便可以輕鬆搜尋姓名。

• 字典 - 字典按字母順序儲存單詞，以便於搜尋任何單詞。

原地排序和非原地排序

排序演算法可能需要一些額外的空間來比較和臨時儲存一些資料元素。這些演算法不需要任何額外的空間，排序據說發生在原地，或者例如，在陣列本身內。這稱為原地排序。氣泡排序就是一個原地排序的例子。

但是，在某些排序演算法中，程式需要的空間大於或等於正在排序的元素。使用等於或更多空間的排序稱為非原地排序。歸併排序就是一個非原地排序的例子。

Java 中的氣泡排序

氣泡排序是一種簡單的排序演算法。這種排序演算法是一種基於比較的演算法，其中比較每對相鄰元素，如果不按順序則交換元素。該演算法不適用於大型資料集，因為其平均和最壞情況的複雜度為 Ο(n2)，其中 n 是專案數。

演算法

我們假設list是一個包含n個元素的陣列。我們進一步假設swap()函式交換給定陣列元素的值。

Step 1: Assume i is the first element of the list then, compare the elements i and i+1. (first two elements of the array)
Step 2: If the i (first element) is greater than the second (i+1) swap them.
Step 3: Now, increment the i value and repeat the same.(for 2nd and 3rd elements) 
Step 4: Repeat this till the end of the array.

示例

import java.util.Arrays;
public class BubbleSort {
   public static void main(String args[]) {
      int[] myArray = {10, 20, 65, 96, 56};      
      System.out.println("Contents of the array before sorting : ");
      System.out.println(Arrays.toString(myArray));
      
      int n = myArray.length;
      int temp = 0;
      
      for(int i = 0; i<n-1; i++) {
         for(int j = 0; j<n-1; j++) {
            if (myArray[j] > myArray[j+1]) {
               temp = myArray[i];
               myArray[j] = myArray[j+1];
               myArray[j+1] = temp;
            }
         }         
      }           
      System.out.println("Contents of the array after sorting : ");
      System.out.println(Arrays.toString(myArray));       
   }
}

輸出

Contents of the array before sorting : 
[10, 20, 65, 96, 56]
Contents of the array after sorting : 
[10, 10, 20, 10, 20]