基数排序(radix sort)

发表于   |   分类于

基数排序(radix sor)的C语言实现。

基数排序，是一种非比较性的正整数排序方法，其算法很简单：

  1. 找出所有数字的最大位数，如42就是2位
  2. 所有数字从最低有效位开始，每个有效位进行一次排序，数位较短的补0
  3. 排序完成之后就得到正确的排序结果

时间复杂度为: O(kN)，k为最大位数。

下面是一个C语言的实现，

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <stdio.h>
#include <stdlib.h> // rand()
#include <math.h>   // pow()

#define SIZE 5000000
#define VERBOSE_DEBUG 0

static int *get_rand_num_array(int size) {
    int *p = (int*)malloc(sizeof(int)*size);
    if(p == NULL)
        printf("error happened when malloc.");
    int i;
    for(i = 0; i < size; i++) {
        p[i] = rand();
    }
    return p;
}

// 是否从小到大排序
static int test_sorted_nums(int *nums, int size) {
    int i;
    for(i = 0; i < size-1; i++) {
        if(nums[i] > nums[i+1]) {
            printf("numbers not sorted.\n");
            return -1;
        }
    }
    printf("numbers sorted.\n");
    return 0;
}

static int get_max_length(int *nums, int size) {
    int max = 1, i;
    for(i = 0; i < size; i++) {
        while(nums[i] >= (int)pow(10, max)) max++;
    }
    return max;
}

void radix_sort(int *nums, int size) {
    int max = get_max_length(nums, size);
    int *tmp = (int*)malloc(sizeof(int)*size);
    int *bucket = (int*)malloc(sizeof(int)*10); // ten numbers, 0...9
    int i, j, radix = 1, *p;
        
    for(i = 1; i <= max+1; i++) {
#if VERBOSE_DEBUG
        for(j = 0; j < size; j++)
            printf(" %d ", nums[j]);
        printf("\n");
#endif
        // 快速清空bucket数组
        memset(bucket, 0, sizeof(int)*10);

        // 统计每个数字(0...9)出现的次数
        for(j = 0; j < size; j++)
            bucket[(nums[j]/radix)%10]++;
        
        // 现在每个bucket[i]中保存的是该数字对应的整数在tmp中
        // 的结尾位置(当然还要加一)
        for(j = 1; j < 10; j++) {
            bucket[j] += bucket[j-1];
        }
        
        // 映射: nums[i] => tmp[j]，bucket中保存着该数字在tmp中的位置
        // 注意倒序，因为bucket[i]中保存的是结尾位置
        for(j = size-1; j >= 0; j--) {
            tmp[(--bucket[(nums[j]/radix)%10])] = nums[j];
        }
        
        // 最后交换两个数组，注意新的tmp数组不用清空
        p = nums;
        nums = tmp;
        tmp = p;
        
        // 进行下一个基数的排序
        radix *= 10;
    }
}

int main()
{
    int *nums = get_rand_num_array(SIZE);
    radix_sort(nums, SIZE);
    test_sorted_nums(nums, SIZE);
    free(nums);
}

(over)