快速排序、線性時(shí)間選擇
摘要: 快速排序是運(yùn)用了分治思想的排序方式，具有O(NlogN)的平均時(shí)間復(fù)雜度，極端情況下時(shí)間復(fù)雜度為O(N^2)，跟冒泡排序一樣，但是快排的實(shí)際效率遠(yuǎn)比最壞情況好很多。它的關(guān)鍵部分是一輪選擇（由Partition()函數(shù)完成）……所謂線性時(shí)間就是在平均O(N)的時(shí)間內(nèi)找出無序序列中第k大的元素。它是以Partition()函數(shù)的劃分為依據(jù)的……
閱讀全文
posted @
2012-07-17 16:46 小鼠標(biāo) 閱讀(3737) |
評(píng)論 (1) 編輯
堆排序
摘要: 堆排序是一種比較常用的排序方式，具有O(NlogN)的時(shí)間復(fù)雜度，它只需要一個(gè)記錄大小的空間，算法的核心是“篩選”。
堆的存儲(chǔ)方式是一維數(shù)組，因?yàn)樗且豢猛耆鏄洌⒆优c雙親下標(biāo)有簡單直接的計(jì)算方式……
閱讀全文
posted @
2012-07-16 11:18 小鼠標(biāo) 閱讀(1183) |
評(píng)論 (0) 編輯