2024q1 Homework2 (quiz1+2)

contributed by < 164253 >

第一周

測驗一

原理

用 quick sort 排序，一個 stack 紀錄哪些區間待排序以省略遞迴呼叫，做到類似 dfs 但加上尾遞迴優化的效果。
每次以第一個元素做 pivot 。

延伸問題:優化

首先要避免的是 quick sort 的最差狀況，也就是正好相反排序時，原因是每次分治兩邊不均勻。
因此可以先找到中位數參照我以前解的一道 leetcode 題目，用 quick select 並自行實作，以三個元素為一組找出中位數，對這

$\lfloor \frac{n}{3}\rfloor$ 個中位數找中位數，並紀錄現在共有多少元素，可以不使用遞迴就實現，最終

$O(n+\frac{n}{3}+\frac{n}{9}+\cdots )=O(n)$ 求出