基数排序

一个基于非比较的排序算法，只能应用于整数排序，复杂度为O(dn)，d是整数最大的长度，即可以在线性时间和线性空间复杂度内完成排序，快于一切基于比较的排序算法，比如快排、归并排序等。

class Solution {
public:
    
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        if(n<2) return 0;
        int ans = 0;
        //sort(nums.begin(),nums.end());

        int mx = -0x3f3f3f3f;
        // 找到最大的整数，决定排序迭代的次数
        for(int i=0;i<n;i++){
            mx = max(mx, nums[i]);
        }
        int x = 1;
        vector<int> tmp(n);

        while(mx>=x){
            // 计数器
            vector<int> cnt(10);
            // 对十进制的每一位进行计数
            for(int i=0;i<n;i++){
                int d = (nums[i]/x)%10;
                cnt[d] ++;
            }
            // 把计数器转换为索引
            for(int i=1;i<10;i++){
                cnt[i] += cnt[i-1];
            }
            // 逆序遍历，对数组进行重新排序
            for(int i=n-1;i>=0;i--){
                int d = (nums[i]/x)%10;
                tmp[cnt[d]-1] = nums[i];
                cnt[d] --;
            }
            // 更新数组
            //copy(tmp.begin(), tmp.end(), nums.begin());
            nums.swap(tmp);
            
            x *= 10;
        }

        for(int i=1;i<n;i++){
            ans = max(ans, nums[i]-nums[i-1]);
        }
        return ans;
    }
};