› 看板 Python 關於我們 聯絡資訊
版上各位前輩好， 小弟是入門者，最近教授出題要寫qsort， 概念是對list選取一pivot， 比他小的都放左邊，大的放右邊， 如此重複，直到完整排序。 我的寫法如下圖： http://i.imgur.com/PyV2XzW.jpg 最後return的時候不知道該怎麼讓遞迴關係在達到排序完畢時停止，不知道要怎麼設條件， 應該說有想到用len=1做停止條件， 但不知道該放在哪裡， 資質駑鈍，還請各位多多指教包涵。 上網查別人寫好的都需要定義很多函式再互相呼叫，還是那才是唯一解呢? 2018/4/16 21:00 感謝各位的回覆 終於開竅了 http://i.imgur.com/sKZFl2f.jpg ----- Sent from my ASUSSSSSSSSSSSSS . 作者: gvi86113 (歐派king) 看板: Python 標題: [問題] Quick Sort陷入無窮遞迴 時間: Sun Apr 15 15:25:33 2018 版上各位前輩好， 小弟是入門者，最近教授出題要寫qsort， 概念是對list選取一pivot， 比他小的都放左邊，大的放右邊， 如此重複，直到完整排序。 我的寫法如下圖： http://i.imgur.com/PyV2XzW.jpg 最後return的時候不知道該怎麼讓遞迴關係在達到排序完畢時停止，不知道要怎麼設條件， 應該說有想到用len=1做停止條件， 但不知道該放在哪裡， 資質駑鈍，還請各位多多指教包涵。 上網查別人寫好的都需要定義很多函式再互相呼叫，還是那才是唯一解呢? ----- Sent from my ASUSSSSSSSSSSSSS . -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.204.97.162 ※ 文章網址: https://www.ptt.cc/bbs/Python/M.1523777136.A.97B.html ※ 編輯: gvi86113 (180.204.97.162), 04/15/2018 15:28:52 ※ 編輯: gvi86113 (180.204.97.162), 04/15/2018 15:46:41 ※ 編輯: gvi86113 (180.204.97.162), 04/15/2018 15:48:05
推 hadoop: list長度為 1 的時候終止遞迴 04/15 16:09
我有想到用len(less_lst) = 1做條件，但沒想到應該要放在哪裡 ※ 編輯: gvi86113 (180.204.97.162), 04/15/2018 16:28:04
→ djshen: 想想看長度1代表什麼 04/15 16:29
我知道長度=1時，代表已經分割到結果了，可是如果要把條件設進去的話，我反而不知道怎麼再次叫出遞迴了，資質駑鈍還請多包涵 QQ
推 hadoop: 放在第一行,直接 return 長度 1 的list 04/15 16:38
設條件之後反而不太清楚遞迴該放在哪裡了，目前寫這樣連自己都覺得不合理 http://i.imgur.com/9oCMBkr.jpg ※ 編輯: gvi86113 (180.204.97.162), 04/15/2018 16:52:52 ※ 編輯: gvi86113 (180.204.97.162), 04/15/2018 16:53:55 ※ 編輯: gvi86113 (180.204.97.162), 04/15/2018 17:00:02
→ djshen: 分割到結果? 你再想想看吧 04/15 20:03
→ bowin: base case: len==1 => return list; 04/15 20:18
→ bowin: take pivot=list[len//2]; 04/15 20:19
→ bowin: return quicksort(list_l)+pivot+quicksort(list_u) 04/15 20:21
→ bowin: list_l = list smaller than pivot; list_u, similarly 04/15 20:22
→ bowin: Soory for quick typo: base case: len<=1 04/15 20:46
→ bowin: Apology for typo: "Sorry"... =_= 04/15 20:47
推 TitanEric: 第一次看到qsort是這樣寫 04/15 21:41
我看到的範例都用好幾個函式互相呼叫 只有我這樣寫嗎qq?
推 vfgce: 你的問題不是qsort,是你根本不會recurion...... 04/15 22:25
因為當下不知道條件怎麼放進去所以就先這樣待補 ><
→ vfgce: recursion要有明確的終止條件,不然就是無限執行.... 04/15 22:26
推 mantour: 你的new_list = ... 那一行的右邊 qsort 應該是打錯了 04/15 23:12
→ mantour: 然後這一行就進入遞迴了 後面的if根本不會被執行到 04/15 23:13
推 mantour: 若 len(L) == 1, qsort(L) 應該 return 什麼 ? 04/15 23:45
推 Kazimir: 你這樣能想的清楚每一層會回傳什麼東西嗎...？ 04/15 23:58
→ Kazimir: https://ideone.com/NWnjCu 我其實也沒寫過 試個 04/16 00:22
推 hihi0123: 資料結構用python上蠻稀奇的 04/16 09:30
→ bowin: MIT EECS也是用Python上Alg & Data Structures 04/16 10:42
感謝各位回覆 我已經找到解決方法了 晚點補上程式碼 ※ 編輯: gvi86113 (49.215.208.192), 04/16/2018 11:35:31 ※ 編輯: gvi86113 (49.215.208.192), 04/16/2018 11:36:41 ※ 編輯: gvi86113 (49.215.208.192), 04/16/2018 11:37:19 ※ 編輯: gvi86113 (49.215.208.192), 04/16/2018 12:52:56 ※ 編輯: gvi86113 (49.215.208.192), 04/16/2018 12:55:33