--- ###### tags: `2020 師大附中資訊科暑期培訓` --- # 排序 2020 師大附中資訊科暑期培訓 joylintp --- ## 選擇排序（Selection Sort） * 找到未排序的部分中最小／最大的數字 * 把該數字與未排序的數字中最左邊的數字交換 * 將未排序的數字中最左邊的數字設成已排序 ---- ```cpp= for (int i = 0; i < n - 1; i++) { int mn = arr[i], mxp = i; for (int j = i + 1; j < n; j++) if (arr[j] < mn) { mn = arr[j]; mxp = j; } swap(arr[i], arr[mxp]); } ``` 複雜度 $O(n^2)$ --- ## 泡沫排序（Bubble Sort） * 將未排序的部分由左到右兩兩比較 * 若右邊的數字較小則將兩數字左右交換 * 將未排序的部分最右邊的數字設為已排序 ---- ```cpp= for (int i = n - 1; i > 0; i--) for (int j = 0; j < i; j++) if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]); ``` 複雜度 $O(n^2)$ --- ## 計數排序（Counting Sort） * 計算各數字的數量 * 將數字由小到大填入陣列 ---- ```cpp= int cnt[1000001] = {}; for (int i = 0; i < n; i++) cnt[arr[i]]++; int id = 0; for (int i = 0; i < 1000001; i++) while (cnt[i]--) arr[id] = i, id++; ``` 複雜度 $O(n + 值域)$ --- ## 合併排序（Merge Sort） * 將陣列遞迴切成左右兩半 * 將兩側排序後依序填回原本陣列 ---- ```cpp= void msort(int l, int r) { if (r == l) return; msort(l, (l + r) / 2); msort((l + r) / 2 + 1, r); queue<int> la, ra; for (int i = l; i <= (l + r) / 2; i++) la.push(arr[i]); for (int i = (l + r) / 2 + 1; i <= r; i++) ra.push(arr[i]); for (int i = l; i <= r; i++) { if (!la.size()) arr[i] = ra.front(), ra.pop(); else if (!ra.size()) arr[i] = la.front(), la.pop(); else if (la.front() <= ra.front()) arr[i] = la.front(), la.pop(); else arr[i] = ra.front(), ra.pop(); } return; } ``` 時間複雜度 $O(n\log{n})$ 額外空間複雜度 $O(n)$ --- ## std::sort ```cpp= #include<algorithm> //... int arr[] = {5, 9, 4, 8, 7}; sort(arr, arr + 5); // 遞增 sort(arr, arr + 5, greater<int>()); vector<int> v; sort(v.begin(), v.end()); ``` 時間複雜度 $O(n\log{n})$ ---- 自訂比較函式： ```cpp= bool cmp(int a, int b) { return a < b; // 若 a 要在 b 前面回傳 true // 否則回傳 false } // ... sort(v.begin(), v.end(), cmp); ```