補(bǔ)充說(shuō)明三點(diǎn)
1,桶排序是穩(wěn)定的
2,桶排序是常見(jiàn)排序里最快的一種,比快排還要快…大多數(shù)情況下
3,桶排序非郴略快,但是同時(shí)也非常耗空間,基本上是最耗空間的一種排序算法
無(wú)序數(shù)組有個(gè)要求,就是成員隸屬于固定(有限的)的區(qū)間,如范圍為[0-9](考試分?jǐn)?shù)為1-100等)
例如待排數(shù)字[6 2 4 1 5 9]
準(zhǔn)備10個(gè)空桶,最大數(shù)個(gè)空桶
[6 2 4 1 5 9]?????????? 待排數(shù)組
[0 0 0 0 0 0 0 0 0 0]?? 空桶
[0 1 2 3 4 5 6 7 8 9]?? 桶編號(hào)(實(shí)際不存在)
1,順序從待排數(shù)組中取出數(shù)字,首先6被取出,然后把6入6號(hào)桶,這個(gè)過(guò)程類(lèi)似這樣:空桶[ 待排數(shù)組[ 0 ] ] = 待排數(shù)組[ 0 ]
[62 4 1 5 9]?????????? 待排數(shù)組
[0 0 0 0 0 060 0 0]?? 空桶
[0 1 2 3 4 567 8 9]?? 桶編號(hào)(實(shí)際不存在)
2,順序從待排數(shù)組中取出下一個(gè)數(shù)字,此時(shí)2被取出,將其放入2號(hào)桶,是幾就放幾號(hào)桶
[6 24 1 5 9]?????????? 待排數(shù)組
[0 020 0 0 6 0 0 0]?? 空桶
[0 123 4 5 6 7 8 9]?? 桶編號(hào)(實(shí)際不存在)
3,4,5,6省略,過(guò)程一樣,全部入桶后變成下邊這樣
[6 2 41 5 9]?????????? 待排數(shù)組
[01 2045 60 09]?? 空桶
[01 2345 6 7 89]?? 桶編號(hào)(實(shí)際不存在)
0表示空桶,跳過(guò),順序取出即可:1 2 4 5 6 9
以下附上用Python實(shí)現(xiàn)的桶排序程序
