基數(shù)排序的方式可以采用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由鍵值的最右邊開(kāi)始,而MSD則相反,由鍵值的最左邊開(kāi)始。
以LSD為例,假設(shè)原來(lái)有一串?dāng)?shù)值如下所示:
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根據(jù)個(gè)位數(shù)的數(shù)值,在走訪數(shù)值時(shí)將它們分配至編號(hào)0到9的桶子中:
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39
接下來(lái)將這些桶子中的數(shù)值重新串接起來(lái),成為以下的數(shù)列:
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接著再進(jìn)行一次分配,這次是根據(jù)十位數(shù)來(lái)分配:
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
接下來(lái)將這些桶子中的數(shù)值重新串接起來(lái),成為以下的數(shù)列:
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
這時(shí)候整個(gè)數(shù)列已經(jīng)排序完畢;如果排序的對(duì)象有三位數(shù)以上,則持續(xù)進(jìn)行以上的動(dòng)作直至最高位數(shù)為止。
LSD的基數(shù)排序適用于位數(shù)小的數(shù)列,如果位數(shù)多的話(huà),使用MSD的效率會(huì)比較好,MSD的方式恰與LSD相反,是由高位數(shù)為基底開(kāi)始進(jìn)行分配,其他的演算方式則都相同。
以LSD為例,假設(shè)原來(lái)有一串?dāng)?shù)值如下所示:
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根據(jù)個(gè)位數(shù)的數(shù)值,在走訪數(shù)值時(shí)將它們分配至編號(hào)0到9的桶子中:
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39
接下來(lái)將這些桶子中的數(shù)值重新串接起來(lái),成為以下的數(shù)列:
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接著再進(jìn)行一次分配,這次是根據(jù)十位數(shù)來(lái)分配:
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
接下來(lái)將這些桶子中的數(shù)值重新串接起來(lái),成為以下的數(shù)列:
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
這時(shí)候整個(gè)數(shù)列已經(jīng)排序完畢;如果排序的對(duì)象有三位數(shù)以上,則持續(xù)進(jìn)行以上的動(dòng)作直至最高位數(shù)為止。
LSD的基數(shù)排序適用于位數(shù)小的數(shù)列,如果位數(shù)多的話(huà),使用MSD的效率會(huì)比較好,MSD的方式恰與LSD相反,是由高位數(shù)為基底開(kāi)始進(jìn)行分配,其他的演算方式則都相同。