wuxiaosi0 2019-12-09
基数排序(radix sort)是一种只适用于数字或字母类型的排序方法,它检查数字或字母的每一位,将之分类,按照位数的特定顺序,来将元素排列。以数字为例,将所有元素按照个位数字分类,分类好后,将个位数字大小排列组合起来,再按照十位数字分类,再按照数字大小排列组合起来,一直到最大数位为止。
基数排序的方式分为2类:
从最高位数上的值开始排序,一轮排序结束后,并没有急着合并整理,而是判断每个桶内的元素,如果桶内的元素大于1个则继续对当前桶进行排序,直到排到最低位数上的值,最终做一次性合并整理,形成排序后的数组。
def BucketSort(arr): max_num = max(arr) i = 0 #(max_num//10**i)%10>0表示当数组中最大的数的最高位没有进行排序前,都一直循环 while (max_num//10**i)%10>0: buckets = [[] for i in range(10)] for num in arr: # (num//10**i)%10获取当前排序的基准数(对应的桶号),如取320的第二个数,则需要放置在2号桶中 bucketIndex = (num//10**i)%10 buckets[bucketIndex].append(num) arr =[] #将桶中的数组从新组合为一个新的数组 for bucket in buckets: arr+=bucket i +=1 return arr
def BucketSortMsd(arr,max_length): if max_length<=0: return arr print("对于当前数组%s按照右起第%s位数排序"%(arr,max_length)) buckets = [[] for i in range(10)] for num in arr: #num // 10 ** (max_length - 1) % 10 ** (max_length) 获取当前数字的桶index bucket_idx = num//10**(max_length-1)%10**(max_length) buckets[bucket_idx].append(num) arr = [] for bucket in buckets: if len(bucket)>2: arr+=BucketSortMsd(bucket,max_length-1) else: arr+=bucket return arr
def BucketSortLetterLsd(arr): sort_arround = len(max(arr)) while sort_arround>=0: buckets = [[] for i in range(26)] for letter in arr: if sort_arround>=len(letter): bucket_index = 0 else: bucket_index = ord(letter[sort_arround])-97 buckets[bucket_index].append(letter) arr = [] for bucket in buckets: arr+=bucket sort_arround-=1 return arr arr = ["banana","apple","orange","ape","he"] print(BucketSortLetterLsd(arr))
根据计算出的桶的索引放置单词,并且放置后按照桶的位置从0-26逐一取出桶中的单词放回序列,然后进行下一轮排序,一直到排序完最后一轮。
1. 不管待排列表是多少个元素,以及元素的长度为多少,都需要创建27个桶,分别对应其他字符以及a-z的26个英文字母
2. 获取待排元素的的最长的单词作为排序的轮数
3. 从低位到高位依次排序(注意:一定是要从地位到高位才能完成我们的字典序)
具体代码分为2个函数,一个函数是获取字母应该放置到哪个桶中,一个函数根据获取的桶的索引将元素放置入桶中
def LetterBucketSortMsd(arr,sort_idx): """sort_idx表示按照给定arr中数组中字母的第几个索引进行排序""" # 如果排序的字母位索引超出最大长度,直接返回数组,如对字母abc按照下标3第4个字母进行排序,这种情况无需排序,直接返回 if sort_idx>len(max(arr)): return arr #建立26个桶 buckets = [[] for i in range(26)] for letter in arr: if len(letter)>sort_idx: #获取桶的索引 bucket_index = ord(letter[sort_idx])-97 else: bucket_index = 0 buckets[bucket_index].append(letter) arr = [] for bucket in buckets: #如果桶中的元素超过2个,则继续排序,最后合并桶 if len(bucket)>=2: arr+=LetterBucketSortMsd(bucket,sort_idx-1) else: arr+=bucket return arr
LSD从低位开始排到高位,每排一位都是把各个桶合并,再按下一位排序;
MSD从高位开始排到低位,排完一位后不合并桶,相同的高位划分子桶继续分配,最后再合并。
堆排序本身没有普适性,仅能用于特定的数组排序,如字母和数字的排序。