大數(shù)據(jù)開(kāi)發(fā)中排序是什么意思

這篇文章主要介紹大數(shù)據(jù)開(kāi)發(fā)中排序是什么意思，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

前面兩篇文章說(shuō)了時(shí)間復(fù)雜度為O(n2)的冒泡排序、插入排序和選擇排序；也說(shuō)了時(shí)間復(fù)雜度為O(nlogn)的歸并排序和快速排序；這次來(lái)說(shuō)一下時(shí)間復(fù)雜度為O(n)的桶排序、計(jì)數(shù)排序和基數(shù)排序，由于它們的時(shí)間復(fù)雜度是線性的，所以它們也叫做線性排序（Linear sort），之所以能夠做到線性復(fù)雜度，是因?yàn)樗鼈冊(cè)谂判虻臅r(shí)候，不涉及元素之間的比較，同時(shí)它們的使用條件也是非?？量痰摹?/p>

桶排序（Bucket sort）

桶排序，顧名思義，用桶來(lái)對(duì)數(shù)據(jù)進(jìn)行分割，桶排序是將要排序的數(shù)組分到幾個(gè)有序的桶里面，然后對(duì)每個(gè)桶里面的數(shù)據(jù)進(jìn)行排序，最后將所有數(shù)據(jù)依次取出，就完成了排序。

來(lái)看一下它的時(shí)間復(fù)雜度，假如將n個(gè)數(shù)據(jù)平均分到m個(gè)桶中，每一個(gè)桶中有x=n/m個(gè)數(shù)據(jù)，每個(gè)桶使用快速排序，時(shí)間復(fù)雜度為O(xlogx)，m個(gè)桶的時(shí)間復(fù)雜度就是O(m*xlogx)，因?yàn)閤=n/m，所以時(shí)間復(fù)雜度為O(nlog(n/m))，當(dāng)桶的個(gè)數(shù)接近數(shù)據(jù)n時(shí)， log(n/m) 將會(huì)是一個(gè)非常小的數(shù)，時(shí)間復(fù)雜度就接近與O(n)了。

但是，上面用了假如兩個(gè)字，因?yàn)橐褂猛芭判蛩枰那疤釛l件比較多，首先數(shù)據(jù)需要很容易就可以劃分到m個(gè)桶中，而且每一個(gè)桶它本身就需要有先后順序，這樣桶就不需要再進(jìn)行排序了。其次，我們上面把均勻兩個(gè)字給加粗了，只有在桶中的數(shù)據(jù)比較平均時(shí)才可以，如果每一個(gè)桶中的數(shù)據(jù)差距是非常大的，那桶內(nèi)排序的時(shí)間復(fù)雜度就不是常量級(jí)了，最極端的情況就是分到了一個(gè)桶中，那時(shí)間復(fù)雜度就變成了O(nlogn)了。

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

假如有10個(gè)G的訂單數(shù)據(jù)，訂單金額都是正整數(shù)，要根據(jù)金額大小進(jìn)行排序，而內(nèi)存又比較小，無(wú)法同時(shí)裝下所有的數(shù)據(jù)該怎么辦？

用桶排序的思路就是，先掃描一遍訂單，看一下大概的金額分布，假如金額都分布在1到1萬(wàn)，我們就可以將金額分到10個(gè)桶里，第一個(gè)桶是1~1000，依此類推，它們的順序依次是0，1，2…9。

理想情況下，就是它們均勻分布在每一個(gè)桶中，然后我們?cè)诿恳粋€(gè)桶中使用快速排序，最后將它們依次輸出出來(lái)。那如果1000-2000的金額比較多的話，還是無(wú)法直接放到內(nèi)存中，那就繼續(xù)使用桶排序進(jìn)行分割，直到全部排序完成。

計(jì)數(shù)排序（Counting sort）

計(jì)數(shù)排序基本上屬于桶排序的特殊情況，在要排序的范圍不大的時(shí)候，比如有x個(gè)數(shù)據(jù)，那我們就分x個(gè)桶，每個(gè)桶內(nèi)的數(shù)據(jù)都是相同的，這樣我們就省下了桶內(nèi)排序的時(shí)間。

至于為什么要叫計(jì)數(shù)，這個(gè)是跟計(jì)數(shù)排序的實(shí)現(xiàn)方法有關(guān)的，不過(guò)我還沒(méi)有理解清楚，這里就先放下了，這個(gè)坑之后再填。

基數(shù)排序（Radix sort）

再來(lái)一個(gè)排序問(wèn)題來(lái)看，如果有十萬(wàn)個(gè)手機(jī)號(hào)碼，要將這十萬(wàn)個(gè)手機(jī)號(hào)從小到大排序。如果使用前面的桶排序和計(jì)數(shù)排序，它的范圍比較大，這兩種算法明顯都不適合。

現(xiàn)在就可以用到第三個(gè)排序方法，基數(shù)排序。在剛剛的問(wèn)題里，我們可以明顯的看出來(lái)，當(dāng)一個(gè)號(hào)碼前面的幾位已經(jīng)明顯大于另一個(gè)號(hào)碼，那后面的也就不需要比較了，也就是說(shuō)我們需要將手機(jī)號(hào)排序?yàn)榈谝粋€(gè)數(shù)字從小到大排序，第一個(gè)數(shù)字相同的，按照第二個(gè)數(shù)字從小到大排序，第二個(gè)數(shù)字相同的，按照第三個(gè)，依此類推，那如何才能排列成這樣呢。

這里我們用一個(gè)新的思路來(lái)考慮，我們先按照最后一位數(shù)字的大小來(lái)進(jìn)行排序，然后再按照倒數(shù)第二位進(jìn)行排序，依此類推，經(jīng)過(guò)11次排序以后，就完成了對(duì)整個(gè)手機(jī)號(hào)的排序。這里需要注意一下的是，必須用穩(wěn)定的排序算法來(lái)實(shí)現(xiàn)，如果是非穩(wěn)定的排序算法，之前的排序就沒(méi)有任何的意義了。

用幾個(gè)字符串表示的話，就是這個(gè)樣子的

再舉一個(gè)訂單的例子，對(duì)于一批訂單，我們希望將它按照金額的大小排序，如果金額相同，就按照下單的時(shí)間進(jìn)行排序，一樣是使用這樣的方法。

那如果我們需要排序的數(shù)據(jù)并不是等長(zhǎng)的，又該如何去處理，比如說(shuō)要對(duì)單詞進(jìn)行排序，有的單詞是五個(gè)字母，有的單詞是十五個(gè)字母，那該如何處理？

我們可以把所有的字母都補(bǔ)到一樣的長(zhǎng)度，不足的后面補(bǔ)0，因?yàn)楦鶕?jù)ASCII碼我們可以發(fā)現(xiàn)，所有的字母都在數(shù)字0之后，它并不會(huì)影響排序的正常進(jìn)行，所以依舊可以使用基數(shù)排序來(lái)進(jìn)行。

以上是“大數(shù)據(jù)開(kāi)發(fā)中排序是什么意思”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對(duì)大家有幫助，更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！