# 基数排序（支持负数）

将无序集合按照个位数大小排序，再按照10位数大小排序，依次增高位数，直到某个位数大于最大数的位数时结束排序。

原始数组：{12,65,34,695,235,2,6,95,46}
按个位排序：
个位是0：{}
个位是1：{}
个位是2：{12，2}
个位是3：{}
个位是4：{34}
个位是5：{65,695,235,95}
个位是6：{6,46}
个位是7,8,9的都是：{}
得到新集合：{12,2,34,65,695,235,95,6,46}
按十位排序：
十位是0：{2,6}
十位是1：{12}
十位是2：{}
十位是3：{34,235}
十位是4：{46}
十位是5：{}
十位是6：{65}
十位是7：{}
十位是8：{}
十位是9：{695,95}
得到新集合：{2,6,12,34,235,46,65,695,95}
按百位排序：
0：{2,6,12,34,46,65,95}
1：{}
2：{235}
...
6:{695}
...
得到新数组：{2,6,12,34,46,65,95,235,695}

inputArr = [199383, 10, 34, -1, -32, -29, 4,
            0, 34, 5, 4, 36, 1, 8, 123, 453, 1008]
print("未排序集合:{0}".format(inputArr))

# 用来存方最大值
max = inputArr[0]
# 位数
deep = 10
while deep <= max:
    # 用来判定是不是已经排序完成了，假如[1,1111111]只需要deep=100即可完成判断，省去deep=1000,10000...的无效循环
    count = 0
    for index in range(1, len(inputArr)):
        # 遍历一遍即可得到最大值，也可以先计算最大值（如果数据太多遍历一遍会比较耗时，所以没有单独计算）
        # 但是多次遍历都会触发比较操作，同样耗时，没有具体测试两种方式的优略，酌情选择吧
        max = (max if(max > inputArr[index]) else inputArr[index])
        # 取绝对值，考虑负数的情况
        if(deep < abs(inputArr[index])):
            count += 1
        tempIndex = index
        while(tempIndex != 0):
            # 计算对应位数的数值
            minItem = inputArr[tempIndex-1] % deep//(deep//10)
            maxItem = inputArr[tempIndex] % deep//(deep//10)

            # py中负数求余会被转换成正数，所以需要转会负数形式
            if(inputArr[tempIndex-1] < 0):
                minItem -= 10
            if(inputArr[tempIndex] < 0):
                maxItem -= 10

            if(maxItem < minItem):
                inputArr[tempIndex-1], inputArr[tempIndex] = \
                    inputArr[tempIndex], inputArr[tempIndex-1]
                tempIndex -= 1
            else:
                break
    if(count == 1):
        break
    deep *= 10

print("已排序集合:{0}".format(inputArr))