#請益 #請益 排序法

7月23日 15:42
最近在複習各種排序演算法 但是發現對於實際的應用不太了解, 想請教各位下面這三種排序方法在實際執行上通常的用途是甚麼?? (可以舉例的話更好) 快速排序法 二元搜尋樹 泡沫排序法
2
回應 11
文章資訊
1 篇文章0 人追蹤
Logo
每週有 30 則貼文
共 11 則留言
長庚大學
用途……都是排序? 有點不太明白妳想要問什麼 泡沫排序法基本上只是用來跟初學者解釋排序法的概念 基本上在實作中是不會使用啦 快速排序法就是一個蠻快的排序法 是可以用的 但其實也是比較偏新手教學用 像 C++ 標準函式庫的 std::sort 使用的就是 quick sort 進一步的改良版 叫 intro sort 至於二元搜尋樹? 妳是指 heap sort 嗎? 如果是的話 時間複雜度跟 quick sort 差不多 但是平均來說慢一點 不過如果在不方便往下遞迴的狀況下 就會比 quick sort 更好
大同大學 資訊工程學系
電商平台 商品價格排序,評價好壞排序 系統層面 以 top 這個指令來說,可以依照 cpu 使用率,記憶體使用率做顯示排序 scheduler 排程也會用到 ( 吧?
B1 噢噢我可能描述的不太對,不是都指排序,所以應該不算heap sort(? 應該是說binary search tree的用途 另外兩個我了解了🙏
B2 不好意思,那如果去以系統層面來說,他們使用上的不同是在哪呢
淡江大學
其實還有很多排序法,像是python內建的排序法Timsort具有stable的特性又可以在最佳O(n)排序完成,最壞還有O(n logn),超神奇的ww 每種排序各有好壞,要在適當的時機使用,而timsort則屬於綜合排序,有merge sort加上insertion sort。 想要找應用可以繼續學「演算法」,就會用到不同的資料結構與排序方法 PS. B7有連結,謝拉ww
國立交通大學
各種排序法的用途就是排序 🤔️ 我猜原 po 是想問什麼情況下該採用哪種算法 一般來說直接用標準函式庫提供的就可以了 要自己開發一套最適合的排序演算法其實要花不少時間 如果不是真的要把效能榨到乾的話 其實我覺得開發排序演算法的成本是可以省下來的 以 C++ 的 std::sort 為例 實作總共包含 quick sort + heap sort + insertion sort + heuristic optimizations 有興趣的話可以參考一些分析 std::sort 的網路文章 光是要看懂就要花很多時間了 直接用標準函式庫的好處是幾乎可以說是 0 開發成本就能在絕大多數的使用情境擁有高效能 如果真的要自己撰寫排序演算法的話 這部分我倒是沒有研究很深 不過大部分情況下 quick sort 也是都有不錯的表現 如果要處理的資料類型滿固定的話 可以找找看有沒有哪個演算法的 best case 剛好適合 比如說 insertion sort 一般都是被當成效能低下的排序演算法 但假設要處理的資料幾乎都是已排序好的 其實 insertion sort 會很快 (根據排序好的程度 甚至會比 quick sort 還快) 除了開發上好寫 實作的程式碼也好讀 其實是一個可行的方案
長庚大學
B5 timsort 平均是 O(nlogn) 喔 best case 才是 O(n) reference:
長庚大學
B6 幾乎已經排序好的時候會接近 O(n) 的 是 insertion sort 吧🤔 這也是為什麼 std::sort 會在 quick sort 遞迴太深的時候 改用 insertion sort 的原因 bubble sort 根本沒在管你排好沒 基本上就是死板的跑完 n * 2 啊
長庚大學
如果要說「什麼情況該採用哪種」 基本上 quick sort 真的是新手會最先接觸到的一批排序法中 最泛用也最快的 不過在一些特殊情況也可能會輸 像是剛才說的 幾乎排好的時候可以用 insertion sort 不適合遞迴的時候可以用 heap sort 隨機存取的成本太高的時候改用 merge sort counting sort 用在當需要被排序的元素範圍很小 例如可能只有 1~10 這十個數字在亂排的時候 而 radix sort 則很適合用在當範圍區間固定的時候 例如 [0-999] 至於妳問到的 二元搜尋樹 其實就是按照特定規則建立的一棵樹 用來讓搜尋更加快速而已 c++ 標準容器的 map 跟 set 都是二元搜尋樹的應用喔
感謝大家的認真回覆,我有點概念了!!謝謝!
國立交通大學
B8 感謝勘誤,已修正