綠的傢俱

[DS] 有關quick與heap sort(Q) The worst case time complexity is O(nlogn) for heap sortand is O(n^2)for quick sort, while their average case timecomplexity are both O(nlogn). Why people prefer quick sort?(Ans) 因為實際上我們要sort的data 大部分都是很亂的(也就是沒有排序過)而且如果data不大的話即使是worst case O(n^2)和O(nlgn) 差異也不大 (以電腦來說幾乎沒感覺)在這部份 quicksort 因為程式較為簡單易寫加上比較Heap 跟quick Big-O 裡面的constant通常主要是Heap的constant較大 因此通常quicksort可以擁有最好的time complexity 再來如果n資料量大並且重複key不高的時候 通常資料會更亂(XD)需要使用heap的機率應該也更低當然也是有部份情況還是以heap sort會較佳 不過都是special case .msgcontent .wsharing ul li { text-indent: 0; } 分享 Facebook Plurk YAHOO! .