摘要: 桶式排序是對(duì)一個(gè)有n個(gè)整型元素的數(shù)組a[n],其中對(duì)任意i，0 <= a[i] <= m的特殊排序算法。
可以對(duì) n==m, n != m分別處理。寫代碼時(shí)需要注意的的是a[i]是訪問第i-1個(gè)元素，而非第i個(gè)。
n != m時(shí)，運(yùn)行時(shí)間為O(m+n),輔助空間為O(m)
n == m時(shí)特殊處理，運(yùn)行時(shí)間為O(N), 輔助空間為O(1)
閱讀全文
摘要: 歸并排序思路：將序列從中間分割成兩部分，分別遞歸歸并排序，后將兩個(gè)子序列合并。
歸并排序雖然是經(jīng)典排序里比較最少的算法，但有大量的復(fù)制操作，還需要O(N)的輔助空間，從而一般不用于主存，也不利于c++編程。
Java中比較操作耗時(shí)多，而復(fù)制則耗時(shí)少，從而歸并排序是Java中主要排序方法。
而在C++ STL中快速排序是基本排序方法。
閱讀全文