一、概述

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

二、相似點(diǎn)

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

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

三、適用場(chǎng)景

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

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

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

四、復(fù)雜度