## 冒泡排序

```cpp
#include <iostream>
#include <vector>

using namespace std;

/**
 * 冒泡排序
 * 平均时间复杂度: O(n^2)
 * 最坏时间复杂度: O(n^2)
 * 最好时间复杂度: 可以立一个flag标记有没有发生交换，如果有序，则不再继续冒泡，所以复杂度可以有O(n)
 * 空间复杂度: O(1)
 * 稳定性: 稳定
 * 排序方式: In-place
 * @param arr
 */
void bubbleSort (vector<int>& arr) {
    int len = arr.size();
    for (int i=len-1;i>=0;i--) {
        for (int j=0;j<i;j++) {
            if (arr[j] > arr[j+1]) swap(arr[j], arr[j+1]);
        }
    }

}

int main() {
    vector<int> arr = {10, 9, 8, 7, 7, 6, 5, 11, 3};

bubbleSort(arr);

for (int &e: arr) cout << e << " ";
}

```

## 选择排序

```cpp
#include <iostream>
#include <vector>

using namespace std;

/**
 * 选择排序
 * 平均时间复杂度: O(n^2)
 * 最坏时间复杂度: O(n^2)
 * 最好时间复杂度: O(n^2)
 * 空间复杂度: O(1)
 * 稳定性: 不稳定
 * 排序方式: In-place
 * @param arr
 */
void SelectionSort (vector<int>& arr) {
    int len = arr.size();
    for (int i=0;i<len;i++) {
        int mn = arr[i];
        int index = i;
        for (int j=i+1;j<len;j++) {
            if (arr[j] < mn) {
                mn = arr[j];
                index = j;
            }
        }

swap(arr[index], arr[i]);
    }

}

int main() {
    vector<int> arr = {10, 9, 8, 7, 7, 6, 5, 11, 3};

SelectionSort(arr);

for (int &e: arr) cout << e << " ";
}

```

## 插入排序

```
#include <iostream>
#include <vector>

using namespace std;

/**
 * 插入排序
 * 平均时间复杂度: O(n^2)
 * 最坏时间复杂度: O(n^2)
 * 最好时间复杂度: O(n), 当有序时，只遍历一次即可
 * 空间复杂度: O(1)
 * 稳定性: 稳定
 * 排序方式: In-place
 * @param arr
 */
void insertionSort (vector<int>& arr) {
    int len = arr.size();
    for (int i=0;i<len-1;i++) { // i 代表已经排好序列的最后一项下表
        int insert = arr[i+1];
        int index = i+1;
        for (int j=i;j>=0;j--) {
            if (arr[j] > insert) {
                arr[j+1] = arr[j];
                index = j;
            } else break;
        }

arr[index] = insert;
    }

}

int main() {
    vector<int> arr = {10, 9, 8, 7, 7, 6, 5, 11, 3};

insertionSort(arr);

for (int &e: arr) cout << e << " ";
}

```

## 归并排序

```cpp
#include <iostream>
#include <vector>

using namespace std;

vector<int> merge (const vector<int>& arr1, const vector<int>& arr2) {
    vector<int> res;

int i = 0;
    int j = 0;
    while (i < arr1.size() && j < arr2.size()) {
        if (arr1[i] < arr2[j]) {
            res.push_back(arr1[i]);
            i++;
        } else {
            res.push_back(arr2[j]);
            j++;
        }
    }

while (i < arr1.size()) {
        res.push_back(arr1[i]);
        i++;
    }

while (j < arr2.size()) {
        res.push_back(arr2[j]);
        j++;
    }

return res;
}

/**
 * 归并排序
 * 平均时间复杂度: O(nlogn)
 * 最坏时间复杂度: O(nlogn)
 * 最好时间复杂度: O(nlogn)
 * 空间复杂度: O(n)
 * 稳定性: 不稳定
 * 排序方式: Out-place
 * @param arr
 */
vector<int> mergeSort (const vector<int>& arr, int start, int end) {

if (end - start <= 1) return vector<int>{arr.begin() + start, arr.begin() + end};

int mid = (end + start) / 2;

vector<int> arr1 = mergeSort(arr, start, mid);
    vector<int> arr2 = mergeSort(arr, mid, end);

return merge(arr1, arr2);

}

int main() {
    vector<int> arr = {10, 9, 8, 7, 7, 6, 5, 11, 3};

vector<int> res = mergeSort(arr, 0, arr.size());

for (int &e: res) cout << e << " ";
}

```

## 快速排序
```cpp
#include <iostream>
#include <vector>

using namespace std;

/**
 * 归并排序
 * 平均时间复杂度: O(nlogn)
 * 最坏时间复杂度: O(n^2)
 * 最好时间复杂度: O(nlogn)
 * 空间复杂度: O(1)
 * 稳定性: 不稳定
 * 排序方式: Out-place
 * @param arr
 */
void quickSort (vector<int> &arr, int start, int end) {
    if (start >= end) return;

int index = start;
    for (int i = start+1; i < end; i++) {
        if (arr[i] < arr[index]) {
            swap(arr[i], arr[index]);
            index++;
            swap(arr[i], arr[index]);
        }
    }

quickSort(arr, start, index);
    quickSort(arr, index+1, end);
}

int main () {
    vector<int> arr = {8, 0, 9, 7, 5, 0, 8, 7, 6, 5, 8, 4, 6, 7, 9, 3, 2, 4};

quickSort(arr, 0, arr.size());

for(int v: arr) cout << v << " ";

return 0;
}
```

逆风起笔