数据结构——排序算法——基数排序

基数排序有两种实现方式。本例属于最高位优先法，思路是从最高位开始，依次对基数进行排序。与之对应的是「最低位优先法」，思路是从最低位开始，依次对基数进行排序。
基数排序可以分为以下三个步骤：
1.找到数组中的最大值，确定最大数字的位数
2.从最低位开始，对数组进行计数排序。计数排序是稳定排序，所以在每一位排序后，相同数值的元素仍然保持相对顺序。
3.重复上述步骤，逐渐向更高位进行排序，直到完成所有位的排序。
4.最终，数组中的元素将按照各个位上的数值排序，从而得到有序数组.

基数排序的时间复杂度是 O(nk)，其中 n 是数组的元素个数，k 是最大数字的位数。它的时间复杂度通常比较稳定，适用于对整数或字符串进行排序。

// 获取数组中的最大值
int getMax(std::vector<int>& arr) {
    int max = arr[0];
    for (int value : arr) {
        if (value > max) {
            max = value;
        }
    }
    return max;
}

// 基数排序的辅助函数，对数组按照指定位数进行计数排序
void countingSort(std::vector<int>& arr, int exp) {
    int n = arr.size();
    std::vector<int> output(n);
    int counting[10] = {0};

    // 统计当前位数上的数字出现次数
    for (int i = 0; i < n; i++) {
        counting[(arr[i] / exp) % 10]++;
    }

    // 计算累计次数
    for (int i = 1; i < 10; i++) {
        counting[i] += counting[i - 1];
    }

    // 构建排序后的输出数组
    for (int i = n - 1; i >= 0; i--) {
        output[counting[(arr[i] / exp) % 10] - 1] = arr[i];
        counting[(arr[i] / exp) % 10]--;
    }

    // 将排序后的结果复制回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// 基数排序函数
void radixSort(std::vector<int>& arr) {
    if (arr.empty()) return;

    int max = getMax(arr);

    // 从最低位到最高位进行排序
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSort(arr, exp);
    }
}


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

对包含负数的数组进行基数排序

// 获取数组中的最大值
int getMax(std::vector<int>& arr) {
    int max = arr[0];
    for (int value : arr) {
        if (value > max) {
            max = value;
        }
    }
    return max;
}

// 基数排序的辅助函数，对非负整数数组按照指定位数进行计数排序
void countingSort(std::vector<int>& arr, int exp) {
    int n = arr.size();
    std::vector<int> output(n);
    int counting[10] = {0};

    // 统计当前位数上的数字出现次数
    for (int i = 0; i < n; i++) {
        counting[(arr[i] / exp) % 10]++;
    }

    // 计算累计次数
    for (int i = 1; i < 10; i++) {
        counting[i] += counting[i - 1];
    }

    // 构建排序后的输出数组
    for (int i = n - 1; i >= 0; i--) {
        output[counting[(arr[i] / exp) % 10] - 1] = arr[i];
        counting[(arr[i] / exp) % 10]--;
    }

    // 将排序后的结果复制回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// 基数排序函数，包含对非负和负数的排序
void radixSort(std::vector<int>& arr) {
    if (arr.empty()) return;

    // 分离正数和负数
    std::vector<int> positive;
    std::vector<int> negative;

    for (int num : arr) {
        if (num >= 0) {
            positive.push_back(num);
        } else {
            negative.push_back(-num); // 负数取相反数
        }
    }

    // 对非负整数排序
    if (!positive.empty()) {
        int maxPositive = getMax(positive);
        for (int exp = 1; maxPositive / exp > 0; exp *= 10) {
            countingSort(positive, exp);
        }
    }

    // 对负数排序
    if (!negative.empty()) {
        int maxNegative = getMax(negative);
        for (int exp = 1; maxNegative / exp > 0; exp *= 10) {
            countingSort(negative, exp);
        }
    }

    // 合并正数和负数
    arr.clear();
    arr.insert(arr.end(), negative.rbegin(), negative.rend());
    arr.insert(arr.end(), positive.begin(), positive.end());
}

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

最高位优先发（MSD）

// 获取数组中的最大值的绝对值
int getMax(std::vector<int>& arr) {
    int max = 0;
    for (int value : arr) {
        if (std::abs(value) > max) {
            max = std::abs(value);
        }
    }
    return max;
}

// 计数排序函数
void countingSort(std::vector<int>& arr, int exp) {
    int n = arr.size();
    std::vector<int> output(n);
    int counting[19] = { 0 };

    // 统计当前位数上的数字出现次数
    for (int i = 0; i < n; i++) {
        int radix = (arr[i] / exp) % 10 + 9; // 转换为正数索引
        counting[radix]++;
    }

    // 计算累计次数
    for (int i = 1; i < 19; i++) {
        counting[i] += counting[i - 1];
    }

    // 构建排序后的输出数组
    for (int i = n - 1; i >= 0; i--) {
        int radix = (arr[i] / exp) % 10 + 9; // 转换为正数索引
        output[--counting[radix]] = arr[i];
    }

    // 将排序后的结果复制回原数组
    std::copy(output.begin(), output.end(), arr.begin());
}

// 最高位优先的基数排序函数，从大到小排序
void radixSortDescending(std::vector<int>& arr, int max) {
    if (arr.empty()) return;

    int exp = 1; // 从最低位开始
    while (max / exp > 0) {
        countingSort(arr, exp);
        exp *= 10;
    }

    // 倒序输出结果，以实现从大到小排序
    std::reverse(arr.begin(), arr.end());
}


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