基数排序

将整数按位数切割成不同的数字，然后按每个位数分别比较,从最低位开始排序。

#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <ctime>
#include <climits>

using std::cout;
using std::endl;
using std::vector;

//只有正整数和0
void radixSort(vector<int>& nums) {
    if(nums.empty()) {
        return;
    }
    int maxNum = INT_MIN;
    for(int num : nums) {
        if(num > maxNum) {
            maxNum = num;
        }
    }
    int maxNunLen = std::to_string(maxNum).size();

    int mod = 10;
    int div = 1;
    vector<vector<int>> bucket;
    for(int i = 0; i < maxNunLen; ++i, mod *= 10, div *= 10) {
        bucket.resize(10);
        for(size_t j = 0; j < nums.size(); ++j) {
            int index = (nums[j] % mod) / div;
            bucket[index].push_back(nums[j]);
        }

        int count = 0;
        for(auto vec : bucket) {
            for(int num : vec) {
                nums[count++] = num;
            }
        }
        bucket.clear();
    }

}

//nums含有负数
void radixSort2(vector<int>& nums) {
    int maxNum = INT_MIN;
    for(int num : nums) {
        if(abs(num) > maxNum) {     //正负数中长的数字
            maxNum = abs(num);
        }
    }
    int maxNunLen = std::to_string(maxNum).size();

    int mod = 10;
    int div = 1;
    vector<vector<int>> bucket;
    for(int i = 0; i < maxNunLen; ++i, mod *= 10, div *= 10) {
        bucket.resize(20);  //更改桶的数量
        for(int j = 0; j < nums.size(); ++j) {
            int index = (nums[j] % mod) / div + 10; //-10~9 映射到下标0~19
            bucket[index].push_back(nums[j]);
        }

        int count = 0;
        for(auto vec : bucket) {
            for(int num : vec) {
                nums[count++] = num;
            }
        }
        bucket.clear();
    }

}

void print(const vector<int>& nums) {
    for(int num : nums) {
        cout << num << ' ';
    }
    cout << endl;
}

void getTestDate(vector<int>& nums) {
    srand(time(nullptr));
    for(int i = 0; i < 10; ++i) {
        nums.push_back(rand()%99);
    }
}


void getTestDate2(vector<int>& nums) {
    srand(time(nullptr));
    for(int i = 0; i < 10; ++i) {
        nums.push_back(rand()%199 - 100);
    }
}

int main() {
    vector<int> nums1;
    getTestDate(nums1);
    print(nums1);
    radixSort(nums1);
    print(nums1);
    
    vector<int> nums2 = {-1234,7, -89, 256};
    print(nums2);
    radixSort2(nums2);
    print(nums2);
}