時(shí)間復(fù)雜度為n的排序算法時(shí)間復(fù)雜度為O(n)的排序算法有許多種，這些排序算法在排序元素?cái)?shù)量較少或者元素已經(jīng)接近有序時(shí)表現(xiàn)良好。下面將介紹其中的三種排序算法：計(jì)數(shù)排序、桶排序和基數(shù)排序。

1.計(jì)數(shù)排序(CountingSort)：

計(jì)數(shù)排序是一種穩(wěn)定的線性時(shí)間復(fù)雜度排序算法。它在排序過程中不需要比較元素的大小，而是利用元素的值作為計(jì)數(shù)數(shù)組的索引，統(tǒng)計(jì)每個(gè)元素的出現(xiàn)次數(shù)，然后根據(jù)計(jì)數(shù)數(shù)組的值將元素放回原數(shù)組。

計(jì)數(shù)排序的步驟如下：

-創(chuàng)建一個(gè)計(jì)數(shù)數(shù)組count，大小為最大元素值加一，并初始化為0；

-遍歷原數(shù)組，統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)，即將元素作為計(jì)數(shù)數(shù)組的索引，對(duì)應(yīng)的計(jì)數(shù)值加一；

-根據(jù)計(jì)數(shù)數(shù)組，重建原數(shù)組排序后的順序。

計(jì)數(shù)排序的時(shí)間復(fù)雜度為O(n)，其中n為原數(shù)組的元素個(gè)數(shù)。但它的空間復(fù)雜度為O(k)，其中k為原數(shù)組中不重復(fù)元素的個(gè)數(shù)。

2.桶排序(BucketSort)：

桶排序是一種線性時(shí)間復(fù)雜度排序算法，它將區(qū)間[0,1)劃分為n個(gè)相同大小的區(qū)間，稱為桶。然后根據(jù)元素的值將元素分配到不同的桶中，再對(duì)每個(gè)桶中的元素進(jìn)行排序。

桶排序的步驟如下：

-創(chuàng)建n個(gè)空桶；

-根據(jù)元素值，將元素放入對(duì)應(yīng)的桶中；

-對(duì)每個(gè)桶中的元素進(jìn)行排序，可以使用其他排序算法如插入排序等；

-按順序?qū)⒚總€(gè)桶中的元素依次放入原數(shù)組中。

桶排序的時(shí)間復(fù)雜度為O(n)，其中n為原數(shù)組的元素個(gè)數(shù)。但桶排序?qū)υ氐囊筝^高，如果元素分布不均勻，則桶排序的效率可能降低。

3.基數(shù)排序(RadixSort)：

基數(shù)排序是一種穩(wěn)定的線性時(shí)間復(fù)雜度排序算法，它根據(jù)元素的位數(shù)進(jìn)行排序。基數(shù)排序可以分為L(zhǎng)SD（LeastSignificantDigit）和MSD（MostSignificantDigit）兩種類型。

LSD基數(shù)排序的步驟如下：

-將所有的元素按照最低位進(jìn)行排序；

-將元素按照次低位進(jìn)行排序，依次類推，直到最高位；

-根據(jù)位數(shù)排序后的元素重新組合成新的數(shù)組。

LSD基數(shù)排序的時(shí)間復(fù)雜度為O(k*n)，其中k為最大元素的位數(shù)，n為原數(shù)組的元素個(gè)數(shù)。但LSD基數(shù)排序在元素的位數(shù)較大時(shí)，可能需要較大的內(nèi)存空間。

這些時(shí)間復(fù)雜度為O(n)的排序算法，對(duì)于小規(guī)模數(shù)據(jù)或者已經(jīng)