一、概述

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

二、相似點

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

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

三、適用場景

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

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

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

四、復(fù)雜度