把数组排成最小的数

RT，很久以前的题，之前考虑的不对，后来偶然在《剑指offer》中看到了解法。

思路就是快排+自己写比较的规则

设有两个串x个y，分别连接成串xy和yx，再按字符串序按位进行比较即可。（之前直接比较了x和y，所以不对）

样例输入：

7
14 36 154 58 36 3 8
9
5534 5226 5636 99956 30 135 35 8 77

样例输出：

1415433636588
135303552265534563677899956

python代码：

#str x,y special compare
def isBigger(x,y):
    str1 = x+y
    str2 = y+x
    #print str1,str2
    #if str1==str2:return True
    _len=len(str1)
    for i in range(_len):
        if i==_len-1:return True
        if str1[i]==str2[i]:continue
        elif str1[i]<str2[i]:return False
        else:return True
    
def partition(array,low,high):
    pivot = array[low]    #list
    while low < high:
        while low < high and isBigger(array[high],pivot):high -= 1
        array[low] = array[high]
        while low < high and isBigger(pivot,array[low]):low += 1
        array[high] = array[low]
    array[low] = pivot
    return low
        
def quickSort(array,low,high):
    if low < high:
        #print low,high
        pivotpos = partition(array,low,high)
        quickSort(array,low,pivotpos-1)
        quickSort(array,pivotpos+1,high)

while True:
    n = input()
    array = raw_input().split()
    quickSort(array,0,len(array)-1)
    print ''.join(array)

把数组排成最小的数

原文：http://blog.csdn.net/messiandzcy/article/details/44566443