<style>

html, body, .ui-content {
background-color: #333;
color: #ddd;

}

body > .ui-infobar {
display: none;
}

.ui-view-area > .ui-infobar {
display: block;
}

.markdown-body h1,
.markdown-body h2,
.markdown-body h3,
.markdown-body h4,
.markdown-body h5,
.markdown-body h6 {
color: #ddd;
}

.markdown-body h1,
.markdown-body h2 {
border-bottom-color: #ffffff69;
}

.markdown-body h1 .octicon-link,
.markdown-body h2 .octicon-link,
.markdown-body h3 .octicon-link,
.markdown-body h4 .octicon-link,
.markdown-body h5 .octicon-link,
.markdown-body h6 .octicon-link {
color: #fff;

}

.markdown-body img {
background-color: transparent;
}

.ui-toc-dropdown .nav>.active:focus>a, .ui-toc-dropdown .nav>.active:hover>a, .ui-toc-dropdown .nav>.active>a {
color: white;
border-left: 2px solid white;
}

.expand-toggle:hover,
.expand-toggle:focus,
.back-to-top:hover,
.back-to-top:focus,
.go-to-bottom:hover,
.go-to-bottom:focus {
color: white;
}

.ui-toc-dropdown {
background-color: #333;
}

.ui-toc-label.btn {
background-color: #191919;
color: white;
}

.ui-toc-dropdown .nav>li>a:focus,
.ui-toc-dropdown .nav>li>a:hover {
color: white;
border-left: 1px solid white;
}

.markdown-body blockquote {
color: #bcbcbc;
}

.markdown-body table tr {
background-color: #5f5f5f;
}

.markdown-body table tr:nth-child(2n) {
background-color: #4f4f4f;
}

.markdown-body code,
.markdown-body tt {
color: #eee;
background-color: rgba(230, 230, 230, 0.36);
}

a,
.open-files-container li.selected a {
color: #5EB7E0;
}

p.img{
text-align:center;
}

</style>
# Bubble Sort
###### tags: `Sort`,`Comparison Sort`
### 介紹
Bubble Sort 透過重複遍歷數列，依序將資料排序。資料進行排序時會依次浮到正確的位置。

<p class = img>圖(一)</p>

如上圖所示，每經過一輪的排序，就會完成一個位置的排序。所以假設今天有 **N** 筆資料要進行排序，總共會需要進行 **(N-1)** 輪比較，且每一輪比較中，都會確定一個位置，因此需要進行比較排序的資料會越來越少。

由此可知，我們會需要一個迴圈控制總共需要比幾輪，還需要一個迴圈去控制每一輪的比較，可以使用雙層 for loop 來實作Bubble Sort。

### 程式碼 :

public static void bubbleSort(int[] arr){
    if(arr.length < 2){ //數列長度小於2直接返回
        return;
    }
    for(int i = arr.length - 1; i > 0; i--){
        boolean isSwap = false; //判斷該輪是否有交換產生
        for(int j = 0; j < i; j++){
            if(arr[j] > arr[j + 1]){
                swap(arr, j, j + 1);
                isSwap = true;
            }
        }
        if(!isSwap){ //若該輪沒有發生交換，表示完成排序
            return;
        }
    }
}

public static void swap(int[] arr, int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

### 參考資料
1. 圖(一)：[VisuAlgo](https://visualgo.net/zh/sorting)
2. [算法大神左神（左程云）带你一周刷爆LeetCode，数据结构算法-leetcode真题解析](https://www.bilibili.com/video/BV1kQ4y1h7ok?p=1)

<hr style="height:1px;border:none;border-top:1px dashed #0066CC;">

[資料結構與演算法](/FP0Vd0lqQM2gDIadctxk2Q)
[Sorting 簡介][0]

[0]:https://hackmd.io/7Mo3SJ1wQ5G8s9PIsu9u_w