python实现计数排序、桶排序和基数排序算法

python实现计数排序、桶排序和基数排序算法

• • • 计数排序
    • • 算法步骤：
    • Python实现计数排序
    • 桶排序
    • • 算法步骤：
    • Python实现桶排序
    • 基数排序
    • • 算法步骤：
    • Python实现基数排序
    • 算法时间复杂度

计数排序

计数排序是一种非比较排序算法，适用于元素范围较小的整数排序。它通过统计每个元素出现的次数，然后根据计数对元素进行排序。

算法步骤：

1. 找出待排序数组中的最大值和最小值。
2. 创建一个计数数组，计数数组的长度为最大值和最小值的差值加一。
3. 统计每个元素在待排序数组中出现的次数，并存储在计数数组的对应位置。
4. 对计数数组进行累加处理。
5. 根据计数数组，将元素放回到原数组的正确位置。

Python实现计数排序

def counting_sort(lst):     if not lst:         return []          min_val = min(lst)     max_val = max(lst)     range_of_elements = max_val - min_val + 1     count_arr = [0] * range_of_elements     output_arr = [0] * len(lst)          for num in lst:         count_arr[num - min_val] += 1          for i in range(1, len(count_arr)):         count_arr[i] += count_arr[i - 1]          for num in reversed(lst):         output_arr[count_arr[num - min_val] - 1] = num         count_arr[num - min_val] -= 1          return output_arr  # 示例 lst = [4, 2, 2, 8, 3, 3, 1] sorted_lst = counting_sort(lst) print("排序后的列表:", sorted_lst) 

桶排序

桶排序适用于均匀分布的浮点数。它将数据分到有限数量的桶里，对每个桶分别排序，最后合并所有桶中的数据得到有序序列。

算法步骤：

1. 设置一个定量的数组当作空桶。
2. 把数组元素分散到各个桶中。
3. 对每个不为空的桶进行排序。
4. 依次从不为空的桶中取出元素。

Python实现桶排序

def bucket_sort(lst):     if len(lst) == 0:         return []          bucket_count = 10     max_value = max(lst)     buckets = [[] for _ in range(bucket_count)]          for num in lst:         index = int(num * bucket_count / (max_value + 1))         buckets[index].append(num)          for bucket in buckets:         bucket.sort()          sorted_lst = []     for bucket in buckets:         sorted_lst.extend(bucket)          return sorted_lst  # 示例 lst = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68] sorted_lst = bucket_sort(lst) print("排序后的列表:", sorted_lst) 

基数排序

基数排序是通过按位排序的方法，首先对最低位进行排序，然后对次低位进行排序，依次进行，直到最高位。基数排序适用于整数或字符串排序。

算法步骤：

1. 找出数组中的最大值，确定排序的位数。
2. 从最低位开始，对每个位进行计数排序。

Python实现基数排序

def counting_sort_for_radix(lst, exp):     n = len(lst)     output = [0] * n     count = [0] * 10          for num in lst:         index = num // exp         count[index % 10] += 1          for i in range(1, 10):         count[i] += count[i - 1]          for num in reversed(lst):         index = num // exp         output[count[index % 10] - 1] = num         count[index % 10] -= 1          for i in range(n):         lst[i] = output[i]  def radix_sort(lst):     max_val = max(lst)          exp = 1     while max_val // exp > 0:         counting_sort_for_radix(lst, exp)         exp *= 10          return lst  # 示例 lst = [170, 45, 75, 90, 802, 24, 2, 66] sorted_lst = radix_sort(lst) print("排序后的列表:", sorted_lst) 

算法时间复杂度

• 计数排序的时间复杂度为O(n+k)，其中n是数组长度，k是数组中元素的范围。适用于范围较小的整数排序。
• 桶排序的时间复杂度为O(n+k)，其中n是数组长度，k是桶的数量。适用于均匀分布的浮点数排序。
• 基数排序的时间复杂度为O(d(n+k))，其中n是数组长度，k是桶的数量，d是位数。适用于整数或字符串排序。

通过以上实现，可以看到这三种排序算法在不同场景下的适用性。计数排序适用于范围较小的整数排序；桶排序适用于均匀分布的浮点数排序；基数排序适用于多位数的整数排序。