1 基數(shù)排序
給定一個序列康聂，對其進行基數(shù)排序匾嘱。基數(shù)指的是早抠，數(shù)字的個位霎烙、十位等等。每一輪的遍歷蕊连，只關(guān)注基數(shù)位置的數(shù)悬垃。
基本思想：不進行關(guān)鍵字的比較，而是依靠“分配”和“收集”甘苍。
算法描述：
準備：數(shù)字0-9“籃子”尝蠕。
- 開始：
- 遍歷基數(shù)（從個位開始）：
- 根據(jù)基數(shù)位置數(shù)的大小，把其放到相應(yīng)的籃子载庭；
- 按照0-9的順序?qū)@子里的數(shù)進行收集看彼；
- 遍歷基數(shù)（從個位開始）：
- 結(jié)束
復(fù)雜度分析：
| 時間復(fù)雜度 | |
|---|---|
| 空間復(fù)雜度 |
分析：時間復(fù)雜度：，M是基數(shù)的個數(shù)囚聚【搁牛空間負責度：
，每個數(shù)籃子顽铸，鏈式存儲茁计。
2 桶排序
給定一個序列，對其進行桶排序谓松。
算法描述：
準備：劃分一定數(shù)量的桶星压。
- 開始：
- 遍歷序列，把數(shù)放到相應(yīng)的桶中鬼譬；
- 對非空的同進行排序（任意排序算法）娜膘。
- 按照順序讀取桶中的元素。
- 結(jié)束
復(fù)雜度分析
| 時間復(fù)雜度 | |
|---|---|
| 空間復(fù)雜度 |
分析：N為排序長度优质，M為桶的個數(shù)竣贪。
- 入桶階段，需要對每個元素劃分的桶進行選擇盆赤，每個元素需要比較
次贾富；
- 排序階段歉眷，每個桶都要進行一次排序牺六，假設(shè)桶內(nèi)元素個數(shù)均勻分布。
- 出桶階段汗捡，每一個桶都要遍歷一次淑际。
3 計數(shù)排序
對一個給定數(shù)值上下限的序列N畏纲，對其進行計數(shù)排序。
算法描述：
準備：初始化一個全為0計數(shù)數(shù)組C春缕。
- 遍歷序列N盗胀，對于每一個遍歷到的數(shù)，數(shù)組C的相應(yīng)位置的值+1锄贼；
- 遍歷數(shù)組C：
- 讀取數(shù)組值票灰，如果該值大于0，循環(huán)：
- 打印出該位置的編號宅荤，值-1屑迂；
- 讀取數(shù)組值票灰，如果該值大于0，循環(huán)：
- 結(jié)束算法。
復(fù)雜度分析
| 時間復(fù)雜度 | |
|---|---|
| 空間復(fù)雜度 |
分析：時間復(fù)雜度：遍歷排序數(shù)組N冯键，遍歷計數(shù)數(shù)組（長度設(shè)為M）惹盼，并循環(huán)N”谷罚空間復(fù)雜度：計數(shù)數(shù)組M手报。
可以看出，這個算法的時間復(fù)雜度是很低的改化，可能超過的極限掩蛤。
計數(shù)排序Leetcode編程練習
