contributed by < paintako >
不用列出上述答案項目,專注於程式碼和背後的原理。
jserv
好的了解
解釋程式碼運作原理
取 list 中第一個 entry 作為 pivot
, 並且移除它
使用 list_for_each_safe
迭代, 需要注意的是, 並且用 itm
作為當前節點, 如果此點小於 pivot
, 將此點移到 list_less
最後, 反之移到 list_greater
中
分成左右兩邊後 ( list_less
以及 list_greater
), 遞迴的下去呼叫 list_sort
,
再將 pivot 加回串列中,並用 list_splice
將 list_less
加到 head
後, pivot
之前再執行 list_splice_tail
將 list_greater
加回結尾完成排序。
改進方案
pivot
挑選問題, 如果原本節點內的排列方式是由大到小, 那此方法的複雜度:
若要改善此問題, 那每次挑 pivot
時可隨機挑選而不是挑固定位置
延伸問題
MAX_DEPTH 512
大小的陣列, 不如在需要增加 stack top
時在 malloc 一塊新的空間給其使用 ( in heap memory) , 這樣可以避免 stack memory
一大塊空間被佔住, 但需要在程式結束前自己手動 free
, 原本的作法離開 function 時系統就會自動回收掉 list_head stack[MAX_DEPTH]
所佔用的記憶體