選擇排序：是一種簡單直觀的排序算法，每次均是選擇最小（大）的元素進行排序。

選擇排序算法思想：1 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置

2 再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾

重復第2步，直到排序完成、時間復雜度為 n^2? 空間復雜度為 1

這種算法的優點是時間復雜度高，并且會改變相同元素的相對位置，因此這個是一種不穩定的排序算法

代碼練習1，對應力扣 顏色分類，代碼見下

class Solution {
public:void selectionSort(vector<int>& a){int n = a.size();for(int i = 0; i<n; ++i){int min = i;for(int j = i+1; j<n; ++j){if(a[min] > a[j]){min = j; }}int tmp = a[min];a[min] = a[i];a[i] = tmp;}} void sortColors(vector<int>& nums) {selectionSort(nums);}
};

冒泡排序：是一種簡單的排序算法，通過多次比較和交換相鄰的元素，將數組中的元素按升序或降序排列

冒泡排序的算法思想：

1 遍歷數組的第一個元素到最后一個元素

2 對每一個元素，與后一個元素進行比較

3 如果順序錯誤，就將他們交換

重復上述步驟，直至數組中的所有元素至少被遍歷過一次

冒泡排序的時間復雜度為0(n^2)，空間復雜度為0(1)

冒泡排序的算法優點：是一種穩定的算法，不會改變相同元素的相對位置，缺點便是效率低下，時間復雜度較高

代碼一，對應力扣，合并兩個有序數組，代碼見下

class Solution {void bubbleSort(vector<int>& a){int n = a.size();for(int i = n-1; i>=0; --i){for(int j=0; j<i; ++j){if(a[j] > a[j+1]){int tmp = a[j];a[j] = a[j+1];a[j+1] = tmp;}}}}
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {for(int i=0; i<nums2.size(); ++i){nums1[m+i] = nums2[i];}bubbleSort(nums1);}
};

代碼2 對應力扣，最后一塊石頭的重量，代碼見下：

class Solution {void bubbleSort(vector<int>& a){int n = a.size();for(int i=n-1; i>=0; --i){for(int j=0; j<i; ++j){if(a[j] > a[j+1]){int tmp = a[j];a[j] = a[j+1];a[j+1] = tmp;}}}}
public:int lastStoneWeight(vector<int>& stones) {while(stones.size() > 1){bubbleSort(stones);int n = stones.size();int v = stones[n-1] - stones[n-2];stones.pop_back();stones.pop_back();if(v || stones.size() == 0){stones.push_back(v);}}return stones[0];}
};

插入排序：工作原理是通過構建有序序列，對于未排序序列，在已排序序列中從后往前掃描，找到對應位置插入，從而使得有序。

算法步驟：1 從第一個元素開始，將它視為已排序部分

2 取出下一個元素，與已排序的元素進行比較

3 如果該元素小于已排序部分的最后一個部分，則將其插入到已排序部分的適當位置，重復 2和3直到完成排序

插入排序的時間復雜度為O(n^2)，空間復雜度為O(1)

代碼練習 1，對應力扣，去掉最低工資和最高工資后的工資平均值，代碼見下

class Solution {void insertSection(vector<int>& a){for(int i=1; i<a.size(); ++i){int x = a[i];int j;for( j=i-1; j>=0; --j){if(x < a[j]){a[j+1] = a[j];}else{break;}}a[j+1] = x;}}
public:double average(vector<int>& salary) {insertSection(salary);int n = salary.size();double sum = 0;for(int i=1; i<n-1; ++i){sum += salary[i];}return sum / (n-2);}
};

代碼 2，對應力扣刪除某些元素后的數組均值，代碼見下

class Solution {void insertionSort(vector<int>& a){for(int i=1; i<a.size(); ++i){int x = a[i];int j;for(j=i-1; j>=0; --j){if(x < a[j]){a[j+1] = a[j];}else{break;}}a[j+1] = x;}}
public:double trimMean(vector<int>& arr) {insertionSort(arr);int n = arr.size();double sum = 0;int cnt = 0;for(int i = n/20; i<n-n/20; ++i){sum += arr[i];cnt++;}return sum/cnt;}
};

代碼 3，學生分數的最小差值，代碼見下

class Solution {void insertionSort(vector<int>& a){for(int i=1; i<a.size(); ++i){int x = a[i];int j;for(j=i-1; j>=0; --j){if(x < a[j]){a[j+1] = a[j];}else{break;}}a[j+1] = x;}}
public:int minimumDifference(vector<int>& nums, int k) {insertionSort(nums);int ret = 100000000;for(int i=0; i + k - 1 < nums.size(); ++i){int l = i;int r = i + k - 1;ret = min(ret, nums[r] - nums[l]);}return ret;}
};