计数排序,桶排序,基数排序的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为常数)