线性时间排序

问题

• 桶排序
  -未完待续…

实现

这些线性排序都是以花费空间复杂度来达到降低时间复杂度的，原理可以看看散列表

桶排序

这里实现的是对数字进行排序，原理是对数字的每一位进行排序；创建一个列表，里面包括了10个list，每一位上的数字只可能是0-9，根据该位上的值来将这些数字存储到相应的list，然后取出这些数字，对下一位进行如上操作，直到排玩最后一位。

#参考 http://www.cnblogs.com/hapjin/p/5534262.html
#桶排序
def bucket_sort(arr,index,num):
    #初始化桶
    ts=[]
    for i in range(10):
        t=[]
        ts.append(t)
    #对指定位排序，入桶
    for i in arr:
        s=str(i)
        if(len(s)<index):
            ts[0].append(i)
        else:
            ts[int(s[len(s) - index:len(s) - index + 1])].append(i)
    #从桶中依次遍历赋给arr
    k=0
    for i in ts:
        for j in i:
           arr[k]=j
           k=k+1
    #回调或退出
    if(index==num):
        return arr
    else:
        return bucket_sort(arr,index+1,num)