---
# System prepended metadata

title: Bubble Sort
tags: [Sort, Comparison Sort]

---

<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 透過重複遍歷數列，依序將資料排序。資料進行排序時會依次浮到正確的位置。

![](https://i.imgur.com/mnlbxoj.gif)
<p class = img>圖(一)</p>

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

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


### 程式碼 : 
```java=
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