Algorithms
摘要: Quicksort是一個很好的比較排序算法，但是其最壞情況運行時間是O(n^2), 還不如Mergesort的O(nlgn),
如何改進(jìn)Quicksort? 答案是：引進(jìn)隨機(jī)化思想。
一種方法： 對給定的待排序序列，隨機(jī)地重排列
另一種方法：隨機(jī)選取pivot
給出第二種方法的代碼
閱讀全文
摘要:
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)個小的元素
最壞運行時間O(n^2)
平均運行時間O(nlgn)
閱讀全文
摘要:
計數(shù)排序?qū)[0],...,a[n-1]進(jìn)行排序，其中1 <= a[i] <= m
計數(shù)排序不是基于比較的排序方法，從而最壞情形下的運行時間也不受比較的排序方法最快O(nlgn)的限制。
計數(shù)排序的運行時間是O(n+m)
閱讀全文
摘要: 桶式排序是對一個有n個整型元素的數(shù)組a[n],其中對任意i，0 <= a[i] <= m的特殊排序算法。
可以對 n==m, n != m分別處理。寫代碼時需要注意的的是a[i]是訪問第i-1個元素，而非第i個。
n != m時，運行時間為O(m+n),輔助空間為O(m)
n == m時特殊處理，運行時間為O(N), 輔助空間為O(1)
閱讀全文
摘要: 歸并排序思路：將序列從中間分割成兩部分，分別遞歸歸并排序，后將兩個子序列合并。
歸并排序雖然是經(jīng)典排序里比較最少的算法，但有大量的復(fù)制操作，還需要O(N)的輔助空間，從而一般不用于主存，也不利于c++編程。
Java中比較操作耗時多，而復(fù)制則耗時少，從而歸并排序是Java中主要排序方法。
而在C++ STL中快速排序是基本排序方法。
閱讀全文
摘要: 快速排序:確定一個樞紐元，一次遍歷后將數(shù)組劃分成兩個部分，第一部分均比樞紐元小，第二部分都比樞紐元大，然后對這兩個數(shù)組進(jìn)行快速排序，是一種遞歸的方法
平均運行時間O(Nlog(N)),最壞運行時間O(N^2)
最壞情形：對于預(yù)排序的序列。
對與樞紐元相等的元素處理：
i,j都停止：會比較相等元素，但是可以劃分成長度相當(dāng)?shù)膬蓚€子數(shù)組
i,j都不停止，不會比較相等元素，但是可能產(chǎn)生長度不平衡的兩個子數(shù)組(與樞紐元相等的元素較多時)樞紐元的選取：
1. 選取第一個元素做樞紐元：對于（部分）預(yù)排序的序列運行時間O(N^2)
2. 隨機(jī)生成樞紐元：能避免上述問題，但是產(chǎn)生樞紐元的代價高
3. 三數(shù)中值分割法：選取左端，右端，中間位置三個元素的中值
閱讀全文