(精华)2020年8月28日 数据结构与算法解析(基数排序)

1、基数排序（Radix Sort）

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

1.1 算法描述

• 取得数组中的最大数，并取得位数；
• arr为原始数组，从最低位开始取每个位组成radix数组；
• 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

1.2 动图演示

1.3 代码实现

/// <summary>
/// 基数排序
/// </summary>
public class Program {

    public static void Main(string[] args) {
        int[] array = { 43, 69, 11, 72, 28, 21, 56, 80, 48, 94, 32, 8 };

        RadixSort(array, 10);
        ShowSord(array);

        Console.ReadKey();
    }

    private static void ShowSord(int[] array) {
        foreach (var num in array) {
            Console.Write($"{num} ");
        }
        Console.WriteLine();
    }

    public static void RadixSort(int[] array, int bucketNum) {
        int maxLength = MaxLength(array);
        //创建bucket时，在二维中增加一组标识位，其中bucket[x, 0]表示这一维所包含的数字的个数
        //通过这样的技巧可以少写很多代码
        int[,] bucket = new int[bucketNum, array.Length + 1];
        for (int i = 0; i < maxLength; i++) {
            foreach (var num in array) {
                int bit = (int)(num / Math.Pow(10, i) % 10);
                bucket[bit, ++bucket[bit, 0]] = num;
            }
            for (int count = 0, j = 0; j < bucketNum; j++) {
                for (int k = 1; k <= bucket[j, 0]; k++) {
                    array[count++] = bucket[j, k];
                }
            }
            //最后要重置这个标识
            for (int j = 0; j < bucketNum; j++) {
                bucket[j, 0] = 0;
            }
        }
    }

    private static int MaxLength(int[] array) {
        if (array.Length == 0) return 0;
        int max = array[0];
        for (int i = 1; i < array.Length; i++) {
            if (array[i] > max) max = array[i];
        }
        int count = 0;
        while (max != 0) {
            max /= 10;
            count++;
        }
        return count;
        //return (int)Math.Log10(max) + 1;
    }

}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
 

1.4 算法分析

基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，当然d要远远小于n，因此基本上还是线性级别的。

基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右。

文章来源: codeboy.blog.csdn.net，作者：愚公搬代码，版权归原作者所有，如需转载，请联系作者。

原文链接：codeboy.blog.csdn.net/article/details/108274769