python计数排序和基数排序算法实例

Python计数排序和基数排序算法实例攻略

计数排序和基数排序是排序算法中比较高效的一类算法，适用于整数排序，具有时间复杂度O(n+k)的优秀特性。本文将为大家详细讲解Python中计数排序和基数排序算法实现的完整攻略。

1. 计数排序算法实现

计数排序的核心思想是统计每个数在序列中出现的次数，然后通过累加计算出每个数所在的位置。具体实现步骤如下：

1. 找到序列中的最大值和最小值，确定计数数组的大小为 max_value - min_value + 1。

2. 统计每个数字出现的次数，计数数组 count 的下标对应数字值，数组中的值则表示该数字值出现的次数。

3. 对于计数数组进行累加操作，即 count[i] += count[i-1]，此操作的目的是确定每个数字值在排序后的序列中所在的位置。

4. 反向扫描原始序列，将每个数字存放到它在排序后的序列中所在的位置。

下面是使用Python实现的计数排序示例代码：

def count_sort(arr):
    """
    计数排序算法实现
    :param arr: 待排序序列
    :return: 排序后的序列
    """
    # 找到序列中的最大值和最小值
    min_value, max_value = min(arr), max(arr)
    # 确定计数数组的大小为max_value - min_value + 1
    count = [0] * (max_value - min_value + 1)
    # 统计每个数字出现的次数
    for num in arr:
        count[num - min_value] += 1
    # 对计数数组进行累加操作
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    # 反向扫描原始序列，将每个数字存放到它在排序后的序列中所在的位置
    result = [0] * len(arr)
    for num in reversed(arr):
        result[count[num - min_value] - 1] = num
        count[num - min_value] -= 1
    return result

2. 基数排序算法实现

基数排序的核心思想是将数字按照位数的大小分成多个桶，每个桶内再按照数字的大小进行排序，最终将桶中的元素按顺序放回原数组中。具体实现步骤如下：

1. 找到序列中最大数字的位数。

2. 根据最大位数依次进行排序操作，对于每个位数，利用计数排序算法将序列按照该位数的大小分成桶，并进行排序操作。

3. 将桶中的元素按顺序放回原数组中。

下面是使用Python实现的基数排序示例代码：

def radix_sort(arr):
    """
    基数排序算法实现
    :param arr: 待排序序列
    :return: 排序后的序列
    """
    # 找到序列中最大数字的位数
    max_digit = len(str(max(arr)))
    # 依次进行排序操作
    for i in range(1, max_digit + 1):
        # 利用计数排序将序列按照该位数的大小分成桶，并进行排序操作
        count = [[] for _ in range(10)]
        for num in arr:
            count[num // 10 ** (i - 1) % 10].append(num)
        arr = [num for bucket in count for num in bucket]
    return arr

3. 示例说明

示例1：计数排序

arr = [3, 1, 4, 1, 2, 7, 5, 2]
sorted_arr = count_sort(arr)
print(sorted_arr) # [1, 1, 2, 2, 3, 4, 5, 7]

以上示例中，输入的序列为 [3, 1, 4, 1, 2, 7, 5, 2]，经过计数排序算法操作后，输出的序列为 [1, 1, 2, 2, 3, 4, 5, 7]。

示例2：基数排序

arr = [3, 1, 4, 1, 2, 7, 5, 2]
sorted_arr = radix_sort(arr)
print(sorted_arr) # [1, 1, 2, 2, 3, 4, 5, 7]

以上示例中，输入的序列同样为 [3, 1, 4, 1, 2, 7, 5, 2]，经过基数排序算法操作后，输出的序列同样为 [1, 1, 2, 2, 3, 4, 5, 7]。

综上所述，本文详细讲解了Python中计数排序和基数排序算法实现的完整攻略，同时给出了两个示例说明。希望能够帮助大家了解和掌握这两种高效的排序算法。