桶排序

基本概念

桶排序（Bucket Sort）：
将待排序元素分散到多个桶中，对每个桶单独排序后合并。

算法步骤

确定桶的数量：根据待排序数组的数值范围，将其划分为 k 个桶，每个桶对应一个特定的区间。
元素分配：遍历数组，将每个元素根据其数值映射到所属的桶中。
桶内排序：对每个非空桶分别进行排序（可选用插入排序、归并排序、快速排序等算法）。
合并结果：按桶的顺序依次合并所有已排序的桶，得到最终有序数组。

内部实现：

class Solution:
	def insertionSort(self,nums:[int])->[int]:
		for i in range(1,len(nums)):
			temp = nums[i]
			j=i
			while j>0 and nums[j-1]>temp:
				nums[j]=nums[j-1]
				j-=1
			nums[j]=temp
		return nums
	def bucketSort(self,nums:[int],bucket_size=n)->[int]:
		nums_min,nums_max=min(nums),max(nums)
		bucket_count = (nums_max-nums_min) // bucket_size+1
		buckets=[[]for _ in range (bucket_count)]
		for num in nums:
			buckets[(num-nums_min)//bucket_size].append(num)
		res=[]
		for bucket in buckets:
			self.insertionSort(bucket)
			res.extend(bucket)
		return res
	def sortArray(self,nums:[int])->[int]:
		return self.bucketSort(nums)

复杂度分析：

指标	复杂度	说明
最佳时间复杂度	$O(n)$	数据分布均匀，每个桶内元素数量相近
最坏时间复杂度	$O(n^2)$	数据集中在少数桶中，桶内排序复杂度高
平均时间复杂度	$O(n+k)$	kk 为桶的数量，数据分布较均匀时接近 O(n)
空间复杂度	$O(n+m)$	需要额外空间存储桶，m 为桶的数量
稳定性	稳定	取决于桶内排序算法，通常使用稳定排序