氣泡排序法是透過反覆的進行「從右至左」兩兩相鄰的數字進行相比後重新排列順序。重新排列的次數取決於輸入的數據,倘若數據是從小排到大,那完全不需要重新排列。
時間複雜度(Time Complexity)
Best Case O(n) | 當資料順序恰巧為小到大時 |
---|---|
Worst Case O(n 2) | 當資料順序為大到小的時候, |
Average Case O(n2) | 第n筆資料,平均比較(n-1)/2次 |
空間複雜度(Space Complexity):θ(1)
穩定性(Stable/Unstable):穩定(Stable)
package practice;
public class BubbleSort {
public static void main(String[] args){
int[] arr = {1,3,5,15,9,12,26,19,37,25,55,76,66};
sorting(arr);
for(int i=0; i<arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void sorting(int[] arr) {
for(int i = arr.length-1; i>0; --i) {
for(int j = 0; j<i; ++j) {
if(arr[j]>arr[j+1]) {
Swap(arr,j,j+1);
}
}
}
}
private static void Swap(int[] arr, int indexA, int indexB) {
int temp = arr[indexA];
arr[indexA] = arr[indexB];
arr[indexB] = temp;
}
}