經典算法:基數排序的小例子

2020-01-18 00:09:03

字體：大中小

來源：轉載

供稿：網友

1.概述

基數排序(Radix sort)是一種非比較型整數排序算法，其原理是將整數按位數切割成不同的數字，然后按每個位數分別比較。由于整數也可以表達字符串（比如名字或日期）和特定格式的浮點數，所以基數排序也不是只能使用于整數。基數排序的發明可以追溯到1887年赫爾曼?何樂禮在打孔卡片制表機(Tabulation Machine)上的貢獻。

原理：將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然后，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以后, 數列就變成一個有序序列。基數排序的時間復雜度是 O(k?n)，其中n是排序元素個數，k是數字位數。

理解：類似【經典算法】第八回：桶排序,這里總是需要10個桶,多次使用，首先以個位數的值進行裝桶,即個位數為1則放入1號桶,為9則放入9號桶，然后再以十位數進行桶排序，依此類推。

如有待排序數組[62,14,59,88,16]簡單點五個數字，分配10個桶,桶編號為0-9,以個位數數字為桶編號依次入桶,變成下邊這樣

| 0 | 0 | 62 | 0 | 14 | 0 | 16 | 0 | 88 | 59 |

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |桶編號

將桶里的數字順序取出來,輸出結果:[62,14,16,88,59]

再次入桶,不過這次以十位數的數字為準,進入相應的桶,變成下邊這樣:由于前邊做了個位數的排序,所以當十位數相等時,個位數字是由小到大的順序入桶的,就是說,入完桶還是有序

| 0 | 14,16 | 0 | 0 | 0 | 59 | 62 | 0 | 88 | 0 |

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |桶編號

因為沒有大過100的數字,沒有百位數,所以到這排序完畢,順序取出即可

最后輸出結果:[14,16,59,62,88]

2.示例

復制代碼代碼如下:

//基數排序 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);