# 2024q1 Homework2 (quiz1+2) contributed by < `164253` > ## 第一周 ### 測驗一 #### 原理 用 quick sort 排序,一個 stack 紀錄哪些區間待排序以省略遞迴呼叫,做到類似 dfs 但加上尾遞迴優化的效果。 每次以第一個元素做 pivot 。 #### 延伸問題:優化 首先要避免的是 quick sort 的最差狀況,也就是正好相反排序時,原因是每次分治兩邊不均勻。 因此可以先找到中位數參照[我以前解的一道 leetcode 題目](https://hackmd.io/wX5w04CuTY-T4hosjmfosw?view#2QuickSelect),用 quick select 並自行實作,以三個元素為一組找出中位數,對這 $\lfloor\frac n3\rfloor$ 個中位數找中位數,並紀錄現在共有多少元素,可以不使用遞迴就實現,最終 $O(n+\frac n3+\frac n9+\cdots)=O(n)$ 求出
×
Sign in
Email
Password
Forgot password
or
By clicking below, you agree to our
terms of service
.
Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Wallet (
)
Connect another wallet
New to HackMD?
Sign up