题目描述

结合计数排序与快速排序方法，变更基本的比较方式，从而获得最终的结果
1.在将整型数组转化为字符串数组的同时，按照字符串第一个字符进行一趟计数排序，第一个字符只能是1-9。
2.对于从1-9子容器里面的数据依次进行快速并并入结果

时间复杂度

这部分省略不算

C++ 代码

class Solution {
public:

string printMinNumber(vector<int>& nums) {
    vector<vector<string>> data(9);
    string s;
    string res;
    for(int i =0;i<nums.size();i++)
    {
        s = to_string(nums[i]);
        int j = s[0]-'1';
        data[j].push_back(s);
    }//计数排序将首字符按1-9放置九个子容器
    for(int i = 0;i<9;i++)
    {
        if(data[i].size()==0) continue;
        quickSort(data[i],0,data[i].size()-1);
        for(int j=0;j<data[i].size();j++)
        {
            res+=data[i][j];
        }
    }
    return res;
}
void quickSort(vector<string>& s,int left,int right)
{
    if(left<right)
    {
        int index = subSort(s,left,right);
        quickSort(s,left,index-1);
        quickSort(s,index+1,right);
    }
}
int subSort(vector<string>& s,int left,int right)
{
    string x = s[left];
    int i = left;
    int j = right;
    while(i<j)
    {
        while(i<j && compare(x,s[j])) j--;
        if(i<j)
        {
            s[i]=s[j];
            i++;
        }
        while(i<j && !compare(x,s[i])) i++;
        if(i<j)
        {
            s[j]=s[i];
            j--;
        }
    }
    s[i]=x;
    return i;
}
bool compare(string &a,string &b) 
{
    if(a+b<b+a) return true;
    else return false;
}

};