一、概述

三種時間復雜度是O(n)的線性排序算法：桶排序、計數排序、基數排序。

二、相似點

這三種排序算法都利用了桶的概念，但對桶的使用方法上有明顯差異：

• 基數排序：根據鍵值的每位數字來分配桶；
• 計數排序：每個桶只存儲單一鍵值；
• 桶排序：每個桶存儲一定范圍的數值；

三、適用場景

桶排序比較適合用在外部排序中。所謂的外部排序就是數據存儲在外部磁盤中，數據量比較大，內存有限，無法將數據全部加載到內存中。

計數排序只能用在數據范圍不大的場景中，如果數據范圍k比要排序的數據n大很多，就不適合用計數排序了。而且，計數排序只能給非負整數排序，如果要排序的數據是其他類型的，要將其在不改變相對大小的情況下，轉化為非負整數。

基數排序對要排序的數據是有要求的，需要可以分割出獨立的“位”來比較，而且位之間有遞進的關系，如果a數據的高位比b數據大，那剩下的低位就不用比較了。除此之外，每一位的數據范圍不能太大，要可以用線性排序算法來排序，否則，基數排序的時間復雜度就無法做到O(n)了。

四、復雜度