摘要: 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函数由指针指向的对象决定调用哪个（运行时决定）
阅读全文