快速排序、線性時間選擇
摘要: 快速排序是運用了分治思想的排序方式，具有O(NlogN)的平均時間復雜度，極端情況下時間復雜度為O(N^2)，跟冒泡排序一樣，但是快排的實際效率遠比最壞情況好很多。它的關鍵部分是一輪選擇（由Partition()函數完成）……所謂線性時間就是在平均O(N)的時間內找出無序序列中第k大的元素。它是以Partition()函數的劃分為依據的……
閱讀全文
posted @
2012-07-17 16:46 小鼠標 閱讀(3688) |
評論 (1) 編輯
堆排序
摘要: 堆排序是一種比較常用的排序方式，具有O(NlogN)的時間復雜度，它只需要一個記錄大小的空間，算法的核心是“篩選”。
堆的存儲方式是一維數組，因為它是一棵完全二叉樹，孩子與雙親下標有簡單直接的計算方式……
閱讀全文
posted @
2012-07-16 11:18 小鼠標 閱讀(1168) |
評論 (0) 編輯