摘要: Quicksort是一個很好的比較排序算法，但是其最壞情況運行時間是O(n^2), 還不如Mergesort的O(nlgn),
如何改進Quicksort? 答案是：引進隨機化思想。
一種方法： 對給定的待排序序列，隨機地重排列
另一種方法：隨機選取pivot
給出第二種方法的代碼
閱讀全文
摘要:
Order Statistics 順序統計
Select(int* a, int n, int ith): 從給定的n個元素中找出第i個小的元素
思想：QuickSort的Partition方法進行分割
如果 i = rank(pivot), 則返回a[k]
如果 i < rank(pivot), 則從前半部分中找第i個小的元素
如果 i > rank(pivot), 則從后半部分中找第i-rank(pivot)個小的元素
最壞運行時間O(n^2)
平均運行時間O(nlgn)
閱讀全文
摘要:
計數排序對a[0],...,a[n-1]進行排序，其中1 <= a[i] <= m
計數排序不是基于比較的排序方法，從而最壞情形下的運行時間也不受比較的排序方法最快O(nlgn)的限制。
計數排序的運行時間是O(n+m)
閱讀全文
摘要:
★ 對于父類函數（virtual、非virtual），如果子類沒有同名函數，則正常繼承
★ 對于父類函數（virtual、非virtual），如果子類有同名函數，無同型函數，則不能調用父類函數
★ 對于父類函數（virtual、非virtual），如果有同型函數：
----非virtual函數由指針類型決定調用哪個
----virtual函數由指針指向的對象決定調用哪個（運行時決定）
閱讀全文