經(jīng)典算法:基數(shù)排序的小例子
1.概述
基數(shù)排序(Radix sort)是一種非比較型整數(shù)排序算法,其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字,然后按每個(gè)位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串(比如名字或日期)和特定格式的浮點(diǎn)數(shù),所以基數(shù)排序也不是只能使用于整數(shù)?;鶖?shù)排序的發(fā)明可以追溯到1887年赫爾曼·何樂(lè)禮在打孔卡片制表機(jī)(Tabulation Machine)上的貢獻(xiàn)。
原理:將所有待比較數(shù)值(正整數(shù))統(tǒng)一為同樣的數(shù)位長(zhǎng)度,數(shù)位較短的數(shù)前面補(bǔ)零。然后,從最低位開(kāi)始,依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個(gè)有序序列?;鶖?shù)排序的時(shí)間復(fù)雜度是 O(k·n),其中n是排序元素個(gè)數(shù),k是數(shù)字位數(shù)。
理解:類似【經(jīng)典算法】第八回:桶排序,這里總是需要10個(gè)桶,多次使用,首先以個(gè)位數(shù)的值進(jìn)行裝桶,即個(gè)位數(shù)為1則放入1號(hào)桶,為9則放入9號(hào)桶,然后再以十位數(shù)進(jìn)行桶排序,依此類推。
如有 待排序數(shù)組[62,14,59,88,16]簡(jiǎn)單點(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ù)字順序取出來(lái),輸出結(jié)果:[62,14,16,88,59]
再次入桶,不過(guò)這次以十位數(shù)的數(shù)字為準(zhǔn),進(jìn)入相應(yīng)的桶,變成下邊這樣:由于前邊做了個(gè)位數(shù)的排序,所以當(dāng)十位數(shù)相等時(shí),個(gè)位數(shù)字是由小到大的順序入桶的,就是說(shuō),入完桶還是有序
| 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)闆](méi)有大過(guò)100的數(shù)字,沒(méi)有百位數(shù),所以到這排序完畢,順序取出即可
最后輸出結(jié)果:[14,16,59,62,88]
2.示例
//基數(shù)排序 C# Code
public static void RadixSort(int[] nums, int digit)
{
for (int k = 1; k <= digit; k++)
{
int[] tmpArray = new int[nums.Length];
int[] tmpCountingSortArray = new int[10];
int i;
for (i = 0; i < nums.Length; i++)
{
int tmpSplitDigit = nums[i] / (int)Math.Pow(10, k - 1) - (nums[i] / (int)Math.Pow(10, k)) * 10;
tmpCountingSortArray[tmpSplitDigit]++;
}
for (i = 1; i < tmpCountingSortArray.Length; i++)
{
tmpCountingSortArray[i] += tmpCountingSortArray[i - 1];
}
for (i = nums.Length - 1; i >= 0; i--)
{
int tmpSplitDigit = nums[i] / (int)Math.Pow(10, k - 1) - (nums[i] / (int)Math.Pow(10, k)) * 10;
tmpArray[tmpCountingSortArray[tmpSplitDigit] - 1] = nums[i];
tmpCountingSortArray[tmpSplitDigit]--;
}
for (i = 0; i < nums.Length; i++)
{
nums[i] = tmpArray[i];
}
}
}
//int[] list = new[] { 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 };
//Sorter.RadixSort(list, 2);
相關(guān)文章
一個(gè)ASP.NET的MYSQL的數(shù)據(jù)庫(kù)操作類自己封裝的
這篇文章主要介紹了一個(gè)ASP.NET的MYSQL的數(shù)據(jù)庫(kù)操作類自己封裝的,在數(shù)據(jù)庫(kù)操作類中的連接字符串中記得加上charset=utf8 需要的朋友可以參考下2014-08-08ASP.NET Core MVC學(xué)習(xí)教程之路由(Routing)
這篇文章主要給大家介紹了關(guān)于ASP.NET Core MVC學(xué)習(xí)教程之路由(Routing)的相關(guān)資料,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家學(xué)習(xí)或者使用ASP.NET Core MVC具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-07-07ASP.NET 運(yùn)行時(shí)錯(cuò)誤: 沒(méi)有為擴(kuò)展名“.asax”注冊(cè)的生成提供程序修正版
ASP.NET 運(yùn)行時(shí)錯(cuò)誤: 沒(méi)有為擴(kuò)展名“.asax”注冊(cè)的生成提供程序。可以在 machine.config 或 web.config 中的 <compilation><buildProviders> 節(jié)注冊(cè)一個(gè)。2009-01-01自動(dòng)類型安全的REST.NET標(biāo)準(zhǔn)庫(kù)refit
這篇文章介紹了自動(dòng)類型安全的REST.NET標(biāo)準(zhǔn)庫(kù)refit,文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-04-04.NET Core/Framework如何創(chuàng)建委托大幅度提高反射調(diào)用的性能詳解
反射是一種很重要的技術(shù),下面這篇文章主要給大家介紹了關(guān)于.NET Core/Framework如何創(chuàng)建委托大幅度提高反射調(diào)用性能的相關(guān)資料,文中通過(guò)示例代碼介紹的非常詳細(xì),需要的朋友可以參考下2018-09-09asp.net源程序編譯為dll文件并調(diào)用的實(shí)現(xiàn)過(guò)程
這篇文章主要介紹了asp.net源程序編譯為dll文件并調(diào)用的實(shí)現(xiàn)過(guò)程,非常有實(shí)用價(jià)值,需要的朋友可以參考下2014-07-07.Net彈性和瞬態(tài)故障處理庫(kù)Polly實(shí)現(xiàn)彈性策略
這篇文章介紹了.Net彈性和瞬態(tài)故障處理庫(kù)Polly實(shí)現(xiàn)彈性策略的方法,文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-06-06