# 氣泡排序bubble sort/內建sort

## infro
$sort$就是一種把一串資料以固定的排序方式排列的一種驗算法
例如：
把1,4,5,2,9,0,3依照非嚴格遞增的方式排列
$\implies$ 0,1,2,3,4,5,9
或是照字典序排列等等

## 氣泡排序法/bubble sort
### 演算法概念
氣泡排序法又稱交換排序法
現在有一個項數為$n$的數列$a_1,a_2....a_n$
從第一項開始，把$a_i$和$a_{i+1}$比較
並且把大的放到i+1項
直到第$a_{n-1}$和$a_{n}$
這樣我們就可以確定$a_n$是正確的
接下來從第一項開始比較直到$a_{n-2}$和$a_{n-1}$

> bubble sort 舞蹈影片 https://youtu.be/Iv3vgjM8Pv4
> wiki bubble sort gif https://upload.wikimedia.org/wikipedia/commons/0/06/Bubble-sort.gif
:::info
:::spoiler 進階內容
第1輪比較n-1次
第2輪比較n-2次
.
.
第n-1輪比較1次
$(n-1) + (n-2) + .... + 1 = n(n-1) / 2$

時間複雜度$O(n^2)$
:::

### 實作

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n = 10;
    int arr[n];
    for(int i = 0; i < n; i++)cin >> arr[i];

    for(int i = n; i > 0; i--){
        for(int j = 0; j < i - 1; j++){
            if(arr[j] > arr[j + 1])swap(arr[j], arr[j + 1]);
        }
    }
    for(int i = 0; i < n; i++)cout << arr[i] << ' ';
}

## 內建sort
在$algorithm$這個標頭檔裡有內建好的排序法
且運行速度非常高，使用也方便
### 語法

sort(arr, arr + n);

:::info
:::spoiler 進階內容
內建sort是用heap sort家quick sort建構的，時間複雜度是$O(nlogn)$

sort()內是放記憶體位置
,前是起始值得記憶體位置
,後是終點值下一個的記憶體位置

一樣的原理也可以用在其他的各種STL中，例如
vector $\implies$ sort(vc.begin(),vc.end());

也可以幫自己建的struct,class排序
也可以自訂比較函式調整排序的方式
>>[自訂比較函式](/0T-V0gkzRCmM0qVQ6JM5Yw)
:::