伊莉討論區

標題: 排序問題 [打印本頁]

作者: s8640920032003 時間: 2023-6-21 09:53 PM 標題: 排序問題

本帖最後由 s8640920032003 於 2023-6-21 09:58 PM 編輯

今天繼續看了資料結構的教學影片

這次看的主題是各種排序演算法的介紹

這主題讓我想到之前有次幫朋友整理了幾百張有2位數編號的卡片

那時候我們用的方式就是MSD Radix sort

不過是人肉版XD 沒辦法用電腦幫忙處理

先從十位數開始分堆->然後再分個位數 (量少的分堆可直接肉眼排)

於是我就一時興起開始想到底這些演算法哪個比較適合人工用呢?

Insertion sort: 看起來人工排還OK，只是桌面要很寬能排成一列 (通過)

Selection sort: 幾百張裡要挑一張最大or最小的......眼睛直接找到脫窗 (淘汰)

Bubble sort: 幾百張慢慢交換，手痠死，卡片也被拿到爛掉 (淘汰)

Counting sort: 還要建每個號碼的counting表，太麻煩了 (淘汰)

Shell sort: 每次還要跳著看，根本NMSL (淘汰)

Quick sort: 還要找東西紀錄兩個index現在到哪了，遞迴的處理方式也有點複雜 (淘汰)

Merge sort: 每次都要從多個run裡面挑最小的，這動作感覺就很煩，沒辦法事先排序每個run，也不可能建selection tree，所以應該只有用2-way merge比較有意義 (淘汰)

Heap sort: 建堆積太麻煩，而且要佔據很大的桌面空間 (淘汰)

LSD Radix sort: 跟原本的MSD類似，只是每一pass還要把所有卡片收起來再分bucket，操作上有點小麻煩但應該還行 (通過)

Distributive counting sort: 同counting sort還要建表 (淘汰)

綜上所述，人工比較能用的只有Insertion sort跟Radix sort

而我們也剛好挑到其中一種

看來人類就算沒學過演算法也會藉由經驗累積自動選出合適的方法(divide and conquer)呢!

歡迎光臨伊莉討論區 (http://a401.file-static.com/)