liyuxia713

基本排序方法及分析（九）：Randomized-Quicksort快速排序的隨機(jī)化版本

     摘要: Quicksort是一個很好的比較排序算法，但是其最壞情況運(yùn)行時間是O(n^2), 還不如Mergesort的O(nlgn),
如何改進(jìn)Quicksort? 答案是：引進(jìn)隨機(jī)化思想。
一種方法： 對給定的待排序序列，隨機(jī)地重排列
另一種方法：隨機(jī)選取pivot

給出第二種方法的代碼  閱讀全文

posted @ 2010-01-24 14:36 幸運(yùn)草 閱讀(3359) | 評論 (0)  編輯

Order Statistics 順序統(tǒng)計（找出第i小元素）

     摘要:
Order Statistics 順序統(tǒng)計
Select(int* a, int n, int ith): 從給定的n個元素中找出第i個小的元素
思想：QuickSort的Partition方法進(jìn)行分割
如果 i = rank(pivot), 則返回a[k]
如果 i < rank(pivot), 則從前半部分中找第i個小的元素
如果 i > rank(pivot), 則從后半部分中找第i-rank(pivot)個小的元素
最壞運(yùn)行時間O(n^2)
平均運(yùn)行時間O(nlgn)   閱讀全文

posted @ 2010-01-21 16:29 幸運(yùn)草 閱讀(1125) | 評論 (0)  編輯

隨機(jī)數(shù)的生成

posted @ 2010-01-21 15:37 幸運(yùn)草 閱讀(497) | 評論 (0)  編輯

基本排序方法及分析（八）：CoungtingSort 計數(shù)排序

     摘要:
計數(shù)排序?qū)[0],...,a[n-1]進(jìn)行排序，其中1 <= a[i] <= m
計數(shù)排序不是基于比較的排序方法，從而最壞情形下的運(yùn)行時間也不受比較的排序方法最快O(nlgn)的限制。
計數(shù)排序的運(yùn)行時間是O(n+m)  閱讀全文

posted @ 2010-01-18 15:50 幸運(yùn)草 閱讀(450) | 評論 (0)  編輯

基本排序方法及分析（七）：HeapSort 堆排序

posted @ 2010-01-18 15:45 幸運(yùn)草 閱讀(645) | 評論 (1)  編輯

類成員函數(shù)繼承（virtual、非virtual）

     摘要:
★ 對于父類函數(shù)（virtual、非virtual），如果子類沒有同名函數(shù)，則正常繼承

★ 對于父類函數(shù)（virtual、非virtual），如果子類有同名函數(shù)，無同型函數(shù)，則不能調(diào)用父類函數(shù)

★ 對于父類函數(shù)（virtual、非virtual），如果有同型函數(shù)：

----非virtual函數(shù)由指針類型決定調(diào)用哪個

----virtual函數(shù)由指針指向的對象決定調(diào)用哪個（運(yùn)行時決定）
  閱讀全文

posted @ 2010-01-08 16:30 幸運(yùn)草 閱讀(5298) | 評論 (0)  編輯

類static成員

posted @ 2010-01-08 12:22 幸運(yùn)草 閱讀(1545) | 評論 (6)  編輯