內(nèi)容來(lái)自尚硅谷Java數(shù)據(jù)結(jié)構(gòu)與java算法（Java數(shù)據(jù)結(jié)構(gòu)與算法）_嗶哩嗶哩_bilibili

寫(xiě)在前面:本文內(nèi)容大致和原視頻內(nèi)老師的筆記內(nèi)容相同，會(huì)偶爾插入自己的注釋和理解，盡量會(huì)完成作業(yè)

7.11基數(shù)排序

7.11.1基數(shù)排序(桶排序)介紹:

?

1.????? 基數(shù)排序(radix sort)屬于“分配式排序”(distribution sort)，又稱(chēng)“桶子法”(bucket sort)或bin sort，顧名思義，它是通過(guò)鍵值的各個(gè)位的值，將要排序的元素分配至某些“桶”中，達(dá)到排序的作用

2.????? 基數(shù)排序法是屬于穩(wěn)定性的排序，基數(shù)排序法的是效率高的穩(wěn)定性排序法

3.????? 基數(shù)排序(Radix Sort)是桶排序的擴(kuò)展

4.????? 基數(shù)排序是1887年赫爾曼·何樂(lè)禮發(fā)明的。它是這樣實(shí)現(xiàn)的:將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。

7.11.2基數(shù)排序的基本思想

1.????? 將所有待比較數(shù)值統(tǒng)一為同樣的數(shù)位長(zhǎng)度，數(shù)位較短的數(shù)前面補(bǔ)零。然后，從最低位開(kāi)始，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后，數(shù)列就變成一個(gè)有序序列。

2.????? 這樣說(shuō)明，比較難理解，下面我們看一個(gè)圖文解釋?zhuān)斫饣鶖?shù)排序的步驟

7.11.3基數(shù)排序的圖文說(shuō)明

將數(shù)組{53,3,542,748,14,214}使用基數(shù)排序，進(jìn)行升序排序

?

第一輪排序：

7.11..4基數(shù)排序代碼實(shí)現(xiàn)

將數(shù)組{53,3,542,748,14,214}使用基數(shù)排序，進(jìn)行升序排序

1.???? 思路分析：前面圖文已經(jīng)講明確

2.???? 代碼實(shí)現(xiàn)

7.11.5基數(shù)排序的說(shuō)明

1.???? 基數(shù)排序是對(duì)傳統(tǒng)桶排序的擴(kuò)展，速度很快.

2.???? 基數(shù)排序是經(jīng)典的空間換時(shí)間的方式，占用內(nèi)存很大，當(dāng)對(duì)海量數(shù)據(jù)排序時(shí)，容易造成OutOfMemoryError 。

3.???? 基數(shù)排序是穩(wěn)定的。[注:假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過(guò)排序，這些記錄的相對(duì)次序保持不變，即在原序列中，r[i]=r[j]且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱(chēng)這種排序算法是穩(wěn)定的;否則稱(chēng)為不穩(wěn)定的]

4.???? 有負(fù)數(shù)的數(shù)組，我們不用基數(shù)排序來(lái)進(jìn)行排序,如果要支持負(fù)數(shù)，參考:

https://code.i-harness.com/zh-CN/q/e98fa9

這個(gè)網(wǎng)頁(yè)里面的內(nèi)容如下：

sorting - sort翻譯 - 基數(shù)排序維基百科

基數(shù)排序?yàn)樨?fù)整數(shù) (4)

我正在嘗試實(shí)現(xiàn)基數(shù)整數(shù)，包括負(fù)整數(shù)。 對(duì)于非負(fù)整數(shù)，我打算創(chuàng)建一個(gè)相應(yīng)的10個(gè)隊(duì)列的隊(duì)列0-9，并實(shí)現(xiàn)LSD算法。 但是我對(duì)負(fù)面的整數(shù)感到困惑。 我現(xiàn)在的想法是繼續(xù)為他們創(chuàng)建10個(gè)隊(duì)列，分別排序，最后給出2個(gè)列表，其中一個(gè)包含負(fù)整數(shù)，另一個(gè)包含非負(fù)整數(shù)。 最后我會(huì)合并它們。

?

你怎么看待這件事？ 是否有更有效的方法來(lái)處理負(fù)整數(shù)？

?

謝謝！

?

另外一個(gè)解決方案是將數(shù)組中的負(fù)數(shù)整數(shù)分開(kāi)，使它們成為正數(shù)，然后使用基數(shù)排序?yàn)檎?，然后反轉(zhuǎn)并附加排序后的非負(fù)數(shù)組。

?

您可以將標(biāo)志視為一種特殊的數(shù)字。 你把單位堆，然后十等，最后在標(biāo)志上。 這確實(shí)會(huì)為底片產(chǎn)生相反的順序，然后您只需反轉(zhuǎn)該底片的內(nèi)容即可。 這是多少年的機(jī)械卡分揀機(jī)工作。

?

請(qǐng)注意，符號(hào)位是有符號(hào)整數(shù)中的最高位，但默認(rèn)情況下，所有數(shù)字均被基數(shù)排序?yàn)闊o(wú)符號(hào)整數(shù)。 所以你需要告訴算法負(fù)數(shù)小于正數(shù)。 在32位有符號(hào)整數(shù)的情況下，可以先排序三個(gè)低位字節(jié)，然后對(duì)符號(hào)位反轉(zhuǎn)的第四個(gè)（高位）字節(jié)進(jìn)行排序，這樣0將用于負(fù)數(shù)而不是1，因此它們將首先排序。

?

我強(qiáng)烈建議按字節(jié)對(duì)數(shù)字進(jìn)行排序，而不是用十進(jìn)制數(shù)字，因?yàn)闄C(jī)器比提取數(shù)字要容易得多。

?

處理帶符號(hào)值的最簡(jiǎn)單方法可能是在最重要的數(shù)字上進(jìn)行操作時(shí)抵消積累的起始位置（即產(chǎn)生位置偏移）。 將所有數(shù)字轉(zhuǎn)換為無(wú)符號(hào)數(shù)據(jù)也是一種選擇，但要求對(duì)數(shù)組數(shù)組至少應(yīng)用兩次（一次準(zhǔn)備輸入，一次還原輸出）。

?

這使用第一種技術(shù)以及字節(jié)大小的數(shù)字（字節(jié)訪問(wèn)通常更高效）：

原諒我不認(rèn)識(shí)這個(gè)語(yǔ)言[s:ac:怕]