這次的Kata是老生常談的——————排序。
在算法領域中蠢莺，排序的知名程度大概僅次于a+b和二分（別問我為什么a+b是算法）雳锋，這么多年以來涌現(xiàn)出了許多經典牛逼的排序算法，比如冒泡趁桃、插入仑最、堆排扔役、桶排、快排词身、二叉樹等等厅目，再加上各種變體，基本該研究的已經被大家研究完了法严。
不過在真正的工作中损敷，我們很少會自己寫排序，一般都是直接用庫函數(shù)深啤，這個Kata的目的就是讓大家練習一下排序算法
拗馒。。溯街。诱桂。洋丐。。
挥等。友绝。。肝劲。
迁客。。
你信嗎辞槐？
還是那句話掷漱，以這個作者的尿性就不可能是純算法題，我們來看看到底是怎么回事榄檬。
題目1
題目1簡單來說就是對整數(shù)排序卜范，整數(shù)的范圍是0~59。
題目2
題目2簡單來說就是對字母排序鹿榜，a~z海雪，所有大寫字母全部轉成小寫。
一桶天下
作者要求用最高效的算法舱殿，看完這倆題目就明白了喳魏，桶排嘛！
很多人以為冒泡是最簡單的排序算法怀薛，錯，最簡單的排序算法其實是桶排迷郑。那么什么是桶排呢枝恋？
桶排，簡單來說就是把所有可能出現(xiàn)的數(shù)據按順序分成一個一個桶嗡害，比如a~z就是26個桶焚碌，拿到輸入數(shù)據之后放到對應的桶里，最后輸出排序結果的時候按順序遍歷桶霸妹，如果有內容就輸出十电，沒有就跳過。
桶排還有一個特點————它是所有算法里面排序效率最高的叹螟，高到什么程度呢————O(1)鹃骂，你敢信？O(1)的排序啊哈哈哈哈罢绽。
優(yōu)點這么明顯畏线，缺點自然也不少。
桶排首先要求輸入數(shù)據必須是離散的良价，而且要提前知道所有可能數(shù)據的排序寝殴，并且需要非常大的存儲空間蒿叠，這個空間大致來說和輸入數(shù)據的可能范圍成正比。也就是說蚣常，桶排是非常極端的空間換時間市咽。
在這兩個題目中，輸入數(shù)據的范圍非常之小抵蚊，所以用桶排那是再合適不過了施绎。
代碼
代碼依然簡單
class BucketSort:
def __init__(self, originList):
self.originList = originList
self.countList = [0 for i in range(len(originList))]
def add(self, item):
if type(item) == type(""):
item = item.lower()
elif type(item) != type([]):
item = [item]
for i in item:
self.countList[self.originList.index(i)] += 1
def result(self):
for i in range(len(self.originList)):
for j in range(self.countList[i]):
print str(self.originList[i]),
print
test = BucketSort([chr(i) for i in range(97, 123)]) # 生成a~z個桶，chr是把ASCII碼轉換成字符
test.add('asdsadasdqwewqedzs')
test.result()
test.add('ASDIHJOIHCJKXHK')
test.result()
這里進行了抽象泌射，同一個類可以解兩道題粘姜。
題外話
桶排的限制有兩點，離散值和空間熔酷。離散值就不說了孤紧，這是硬傷，但是空間在未來可能不再是限制拒秘。
來看一個GitHub上的項目pifs号显，這個項目名字翻譯過來就是π文件系統(tǒng)，我簡單解釋一下躺酒。
π是一個無限不循環(huán)小數(shù)押蚤，它還有一個特性就是平凡，意思是0~9這九個數(shù)字在π中出現(xiàn)的概率相同羹应，這點已經被證明過了揽碘。
大家都知道，計算機中的各種數(shù)據本質上都是二進制园匹，所以可以轉換成10進制雳刺，由于π是無限不循環(huán)的，所以理論上任何裸违，注意我說的是“任何”數(shù)據掖桦，都可以在π中找到一模一樣的一段。
也就是說供汛，π里面包含所有我們用到和沒用到的數(shù)據枪汪，包含windows，包含Linux怔昨，也包含你電腦上的任意一個文件雀久。
但是如果把π看作一個文件系統(tǒng)，會有兩個問題：讀和寫朱监。
先說寫岸啡，寫的意思就是給定一段數(shù)據，找到這段數(shù)據在π中出現(xiàn)的位置以及長度赫编，這個問題其實是π文件系統(tǒng)的核心問題巡蘸，由于π是無限不循環(huán)奋隶，計算速度有限，所以找到位置目前來說非常困難悦荒。
再說讀唯欣，讀就簡單多了，假設已經知道數(shù)據出現(xiàn)的位置和長度搬味，可以直接進行計算境氢。之所以不用一位一位算下去，是因為有一個牛逼的數(shù)學家提出了一個牛逼的公式碰纬，可以直接計算π的第n位萍聊，跳過前n-1位。
前面說的GitHub項目悦析，就是實現(xiàn)了一個簡單的π文件系統(tǒng)寿桨，已經可以使用了哦，只不過據作者說强戴，存一個400行的文件進去也需要計算很長時間才能找到位置亭螟。。骑歹。
我想說的是预烙，這個想法絕對是顛覆性的，計算能力在不斷提升道媚，科學也在不斷發(fā)展扁掸，一旦未來我們能快速找出數(shù)據位置，那存儲就再也不是難題最域。到那時我們將擁有近乎無限的數(shù)據存儲空間也糊，所有的數(shù)據都在π中，所以無論文件有多大羡宙，我們的系統(tǒng)只需要存儲它在π中的位置和長度這兩個字段即可。
當時看到這個項目的時候我非常激動掐隐，這種看到未來的感覺狗热，我相信你們也會喜歡的。
