liyuxia713

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

類static成員

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