Sword finger offer 45. arrange the array into the smallest number

The finger of the sword Offer 45. Make the array the smallest number https://leetcode.cn/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/

First, let's talk about quick sorting

Fast sorting algorithm _ The harder you work, the luckier your blog -CSDN Blog https://blog.csdn.net/qq_37891604/article/details/125902608?spm=1001.2014.3001.5501 that , For this question , Just add the sorting rule to the quick sort

This problem is to find the smallest number spliced together , It's essentially a sort problem . Set array numsnums The string of any two numbers in is x and y , It stipulates that Sorting judgment rule by ：

If you splice strings x + y > y + x , be x Should be in y On the right  ;
conversely , if x + y < y + x , be x Should be in y On the left  ;
 

class Solution:
    def minNumber(self, nums):
        def qsort(l,r):
            if l>=r: return
            i,j,key=l,r,strs[l]
            while i<j:
                while i<j and strs[j]+key>=key+strs[j]:
                    j-=1
                strs[i],strs[j]=strs[j],strs[i]
                while strs[i]+key<key+strs[i]:
                    i+=1
                if i>=j:break
                strs[i], strs[j] = strs[j], strs[i]
            qsort(l, j-1)
            qsort(j+1, r)
        strs=[str(i) for i in nums]
        qsort(0,len(strs)-1)
        return ''.join(strs)