Sorting

前言： 在開始練習各種演算法題型時，最先需要養成的是，如何選用「適當」的演算法，題目往往不會只有一種解，但合適的演算法可以如同走捷徑一般，快速且優雅的達到目標。 在實作程式前，更重要的是，寫下一段 pseudo code，試著說明其複雜度，並觀察是否有冗餘的空間可以優化。 在腦海中模擬一遍程式碼之後，最後才是快速的將程式碼實作出來。 在這一章節，我們將練習如何將「想法」轉換成「實作」。並且我們必須熟悉如何計算其時間複雜度。 一、Cheat Table 首先我們需要先瞭解每一種資料結構的各種操作的時間複雜度，以便我們選擇適合的資料結構與演算法。 下面這種表的 Array, Stack, Queue, Linked List, Hash Table, Binary Search Tree 基本上是要背起來的，其餘的遇到再去認識就好。 接下來就輪到練習實作了，排序演算法是個很好的練習，試著把下表中的排序演算法完成，並且計算其時間複雜度吧。 參考題目 Leetcode 912. Sort an Array 二、Sorting Algorithm 0. 測資 這個 file 是我寫的測資，可以拿來測試自己的實作，用法是 #include "agtr.h"，之後用 judge() 函式測試你寫好的 function。 #include <iostream> #include <random> #include <vector> using namespace std; class agtr{ public: static vector<int> exec(int n, int minv, int maxv) { if (minv > maxv) return {}; else if (minv == maxv) return vector<int>(n, minv); vector<int> res; random_device rd; mt19937 mt(rd()); uniform_real_distribution<double> dist(minv, maxv); while (n--) { res....