基数排序-最低位优先法#

算法思维#

基数排序是一种非比较型的排序，其原理是把数字按位数分割，然后对每一位进行分配和收集
最低位优先法就是从数字的最低为开始，依次分配和收集
最低位优先法相较于最高位优先法，最低位优先法不需要分子序列

算法设计#

确定数字最高位数
对每个数字的每一位从低位到高位进行下面操作
先按照位数大小进行分配，然后按照排列顺序进行收集，根据分配收集的特性，可以用队列来实现

算法实现#

1
// 基数排序，最高位优先法
2
/*
3
len_number：数字最长位数
4
*/
5
void sort_radixSort_MSD(int* arr, int len, int len_number, int mode)
6
{
7
    // 创建头指针
8
    SNode* arr_list = createSNode(-1);
9
    addSListToTheNext(arr_list, createList(arr, len));
10

11
    // 记录头地址
12
    SNode* arr_list_head = arr_list;
13
    SNode* node_tmp;
14

15
    // 初始化关键码数组
16
    Queue** digit_arr[10];
17
    for(int i = 0; i < 10; i ++) digit_arr[i] = createQueue();
18

19
    // 用来截取关键码
20
    int flag = 1;
21
    int flag_tmp = 1;
22

23
    // 存放关键码
24
    int digit_tmp;
25
    while(flag_tmp++ <= len_number)
26
    {
27
        // 将数字按关键码排好
28
        while(arr_list->next)
29
        {
30
            node_tmp = deleteNextSNode(arr_list);
31
            digit_tmp = node_tmp->value / flag % 10;
32
            queue_push(digit_arr[digit_tmp], node_tmp);
33
        }
34

35
        // 按顺序从关键码数组中取出数据
36
        for(int i = 0; i < 10; i ++)
37
        {
38
            while(node_tmp = queue_pop(digit_arr[mode? i : (9 - i)]))
39
            {
40
                addSNodeToTheNext(arr_list, node_tmp);
41
                arr_list = arr_list->next;
42
            }
43
        }
44

45
        // 把地址重新赋值
46
        arr_list = arr_list_head;
47
        flag *= 10;
48
    }
49

50
    // 把相应的值赋给数组
51
    for(int i = 0; i < len; i ++)
52
    {
53
        arr[i] = deleteNextSNode(arr_list)->value;
54
    }
55
}

运算结果#

测试代码

1
#define N 10
2

3
int main()
4
{
5
    int arr[N] = {278,109,63,930,589,184,505,269,8,83};
6

7
    sort_radixSort_MSD(arr, N, 3, 1);
8
    utils_print_arr(arr,0, N-1, "%2d ","升序排列结果:\n", "\n\n");
9

10
    sort_radixSort_MSD(arr, N, 3, 0);
11
    utils_print_arr(arr,0, N-1, "%2d ", "降序排列结果:\n", "\n");
12

13
    return 0;
14
}

运算结果

其他#

最低位优先法动态图图片来源

原文链接：CSDN