經(jīng)典排序算法 - 基數(shù)排序Radix sort
原理類似桶排序,這里總是需要10個(gè)桶,多次使用
首先以個(gè)位數(shù)的值進(jìn)行裝桶,即個(gè)位數(shù)為1則放入1號(hào)桶,為9則放入9號(hào)桶,暫時(shí)忽視十位數(shù)
例如
待排序數(shù)組[62,14,59,88,16]簡單點(diǎn)五個(gè)數(shù)字
分配10個(gè)桶,桶編號(hào)為0-9,以個(gè)位數(shù)數(shù)字為桶編號(hào)依次入桶,變成下邊這樣
| 0 | 0 | 62 | 0 | 14 | 0 | 16 | 0 | 88 | 59 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |桶編號(hào)
將桶里的數(shù)字順序取出來,
輸出結(jié)果:[62,14,16,88,59]
再次入桶,不過這次以十位數(shù)的數(shù)字為準(zhǔn),進(jìn)入相應(yīng)的桶,變成下邊這樣:
由于前邊做了個(gè)位數(shù)的排序,所以當(dāng)十位數(shù)相等時(shí),個(gè)位數(shù)字是由小到大的順序入桶的,就是說,入完桶還是有序
| 0 | 14,16 | 0 | 0 | 0 | 59 | 62 | 0 | 88 | 0 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |桶編號(hào)
因?yàn)闆]有大過100的數(shù)字,沒有百位數(shù),所以到這排序完畢,順序取出即可
最后輸出結(jié)果:[14,16,59,62,88]
代碼僅供參考
static void Main(string[] args)
{
int[] x = { 999999999, 65, 24, 47, 13, 50, 92, 88, 66, 33, 22445, 10001, 624159, 624158, 624155501 };
radix_sort(x);
foreach (var item in x)
{
if (item > 0)
Console.WriteLine(item + ",");
}
Console.ReadLine();
}
新聞熱點(diǎn)
疑難解答
圖片精選