vlambda博客
学习文章列表

计数排序,桶排序,基数排序的python实现

计数排序,基数排序,桶排序都属于非比较排序算法,待排序列中的元素本身含有了定位特征,平均时间复杂度都是O(n)。这三种排序算法都利用了桶的概念,对桶的使用方法上有明异如下。

  • 计数排序:每个桶存储单一的键值;

  • 桶排序:每个桶存储某一区间范围的键值;

  • 基数排序:根据键值每一位上的值来分配桶;

1.计数排序

计数排序用来对有确定范围的整数进行排序,计数的序列M (即桶) 的长度取决于待排序列中数据值的范围(长度>=max-min+1),当输入的元素是 n 个 0 到 m 之间的整数时,它的运行时间是 O(n + m)。对于数据范围很大的序列,时间和内存消耗大,适用性不高。


该算法将输入的数值转化为键存储在额外开辟的序列空间中,步骤如下:

1) 找出原始序列中最大的元素max(arr)与最小元素min(arr),开辟新的序列bucket长度至少为max-min+1;

2) 统计序列arr中值为i的元素出现的次数(计数累加),存入数组bucket的第(i-min1)项;

3) 从头开始填充目标序列arr,将每个元素j按顺序放在序列arr中,每放一个就将j元素的个数bucket[j]减去1。

#计数排序def CountingSort(arr): max1=max(arr) min1=min(arr) n1=max1-min1+1 #max函数找出值最大的元素 bucket = [0]*n1 #初始化桶 sort_index =0  for i in arr:        bucket[i-min1]+=1   #统计数值为i的次数并存入桶中,并对计数累加  for j in range(n1): while bucket[j]>0: arr[sort_index] =j+min1 sort_index+=1 bucket[j]-=1    return arr
if __name__=='__main__': arr=[9,3,4,1,17] CountingSort(arr) print(arr)


2.桶排序

也称箱排序,它将序列元素划分到有限数量的桶里,对每个桶的元素再分别在桶内使用其他的排序算法进行排序,最后合并各个桶内的元素

#桶排序def BucketSort(waitarray, bucketsize): minv = min(waitarray) maxv = max(waitarray)  count = (maxv - minv+1) // bucketsize+1 #桶数量 bucket_array = [ [] for c in range(count)] #初始化桶
for k in waitarray: index = (k - minv+1) // count        bucket_array[index].append(k)       #将各元素按照区间放入桶中 buffer_bucket_array=[]
for j in bucket_array: #桶内使用快速排序 n=quicksort(j) buffer_bucket_array.append(n) array_end = [] for j in buffer_bucket_array: #按照桶的顺序合并数据 if len(j) > 0: array_end.extend(j) return array_end
#快速排序:def quicksort(array): if len(array)<2: return array else: pivot=array[0] array.remove(pivot) # 从原数组中移除基准值,对相同元素排序,避免出现无限递归 less=[x for x in array if x <= pivot] more=[x for x in array if x > pivot] return quicksort(less)+[pivot]+quicksort(more)
if __name__=='__main__': arr=[0,-1,10,3,1,4,6,4] print(arr) print(BucketSort(arr,3)) #给定待排数组或列表,每个桶内装3个元素

1)根据待排序列的最大值和最小值的差值范围以及每个桶的元素数量,确定桶的个数;

2)遍历待排序序列,将每个元素放入相对应的桶中;

3)在每个桶中对其中的元素进行排序(此处选择快速排序算法);

4)合并每个桶中的元素,完成排序。


补充:在此修正之前的快速排序算法,添加了(第30行) array.remove(pivot)  ,目的是从原序列中移除基准值,对相同元素排序可避免出现无限递归】


桶排序的时间复杂度:O(n+n(logn-logm)),空间复杂度:O(n+m)

其稳定性取决于桶内元素排序时所使用算法的稳定性,快速排序为不稳定排序算法,此处的桶排序不稳定。


3.基数排序

基数排序适用于非负整数序列,其中的最低位优先(Least Significant Digit first)法,简称LSD法,从最低位开始,依次进行一次稳定排序,从最低位直到最高位进行排序,使得整个序列变成有序序列。

例如:序列 5, 60, 27, 423, 111 有如下排序过程:

第一次从个位,060       111      423      005      027

第二次从十位,005       111      027      423      060

第三次从百位,005       027      060      111      423

最终结果,5,27,60,111,423 排序完成。


def RadixSort(array): m = 0 # 记录当前正在考虑的位,从最低位开始 maxvalue = max(array)     n = len(str(maxvalue))  # 记录最大值的位数
while m<n: bucket_array =[[] for _ in range(10)] #数字范围0-9,因此有初始化10个桶 for i in array:            bucket_array[int(i / (10**m)) % 10].append(i) # 依据元素i在m位的值,在桶中找到位置 #print(bucket_array) array.clear() for x in bucket_array: # 将一次排序后的元素再依次放回原序列中 for y in x:i array.append(y) m= m+1 #准备依据更高一位的位值进行下一次排序 return array
if __name__ == '__main__': a = [334,5,67,345,7,345345,99,4,23,78,45,1,3453,23424] b=RadixSort(a) print(a) print(b)


总结:

排序算法 时间复杂度
空间复杂度
稳定性
计数排序
O(n + m) O(n+m) 稳定
桶排序
O(n+n(logn/m)) O(n+m) 取决于桶内排序算法
基数排序
O(n*m) O(n+m) 稳定

(m为常数)