Re: [問題] 新手return範例問題

作者: john0126 (彈小男孩的木吉他)   2017-09-12 22:02:51
踏入不到一個月的新手,嘗試回答一下,有錯誤的話請多指教。
: def quicksort(arr):
: if len(arr) <= 1:
: return arr
若 len(arr) <= 1 ,則不需排序,直接 return arr。
: pivot = arr[len(arr) // 2]
取 arr[len(arr) // 2 ] 作為關鍵的比較值,但其實我覺得無所謂,
直接用 arr[0] 也可以,不確定是否在數量太大時會影響執行速度?
: left = [x for x in arr if x < pivot]
只要比 pivot 小的,通通丟進 left
: middle = [x for x in arr if x == pivot]
與 pivot 相等的值
: right = [x for x in arr if x > pivot]
比 pivot 大的,通通丟進 right
: return quicksort(left) + middle + quicksort(right)
: print(quicksort([3,6,8,10,1,2,1]))
所以在這個例子裡:
首先 len(arr) // 2 為 3 ,故 pivot = arr[3] = 10
會回傳 quicksort([3,6,8,1,2,1]) + [10] + quicksort([])
然後如 stucode 大所說的,會持續遞迴呼叫 quicksort(),繼續排序。
作者: uranusjr (←這人是超級笨蛋)   2017-09-12 23:44:00
取中間的好處是可以讓左右兩個列表大小比較平均一點因為實際應用中資料通常不會完全無序而是 partly sorted講錯, 不是大小是排序需要用的步驟數
作者: john0126 (彈小男孩的木吉他)   2017-09-13 00:49:00
原來如此!感謝!

Links booklink

Contact Us: admin [ a t ] ucptt.com