python 计数排序 代码示例

当然，这是一个简单的 Python 计数排序的代码示例：

def counting_sort(arr):
    max_value = max(arr)  # 找到数组中的最大值
    count =  * (max_value + 1)  # 创建一个计数数组，初始值为0

    for num in arr:
        count[num] += 1  # 统计每个元素的出现次数

    sorted_arr = []
    for i in range(len(count)):
        sorted_arr.extend([i] * count[i])  # 根据计数数组重新构建排序后的数组

    return sorted_arr

这个函数 `counting_sort` 接受一个整数数组 `arr` 并返回排序后的数组。它首先找到数组中的最大值，然后创建一个计数数组 `count`，并初始化为0。然后遍历原始数组 `arr`，计算每个元素出现的次数并在计数数组中相应位置加1。最后，根据计数数组重新构建排序后的数组 `sorted_arr`，并返回该数组。

请注意，计数排序适用于非负整数排序，并且在输入数组中元素值范围不大时效率较高。

相关问题

python 基数排序 代码示例

当然，这是一个示例的基数排序的Python代码：

def countingSort(arr, exp1):
    n = len(arr)
    output =  * n
    count =  * 10

    for i in range(0, n):
        index = arr[i] // exp1
        count[index % 10] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    i = n - 1
    while i >= 0:
        index = arr[i] // exp1
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1

    i = 0
    for i in range(0, len(arr)):
        arr[i] = output[i]


def radixSort(arr):
    max_value = max(arr)

    exp = 1
    while max_value // exp > 0:
        countingSort(arr, exp)
        exp *= 10


# 示例使用：
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radixSort(arr)

print("排序结果:")
for i in range(len(arr)):
    print(arr[i], end=" ")

这个代码示例中，`radixSort` 函数实现了基数排序算法。`countingSort` 函数是用于计数排序的辅助函数。示例使用了一个整型数组 `arr` 来进行排序，并输出排序后的结果。你可以根据需要修改输入数组 `arr` 的值来测试不同的输入。

python 计数排序

计数排序（Counting Sort）是一种非比较型整数排序算法，它对输入的数据进行计数，然后根据计数值直接输出排序结果。计数排序适用于数据规模较小且数据分布均匀的情况，它的时间复杂度为O(n+k)，其中n是输入数据的数量，k是输入数据的最大值。

在Python中实现计数排序的代码示例如下：

def counting_sort(arr):
    # 确定最大值和计数数组的长度
    max_val = max(arr)
    count_len = max_val + 1
    # 初始化计数数组
    count =  * count_len
    # 统计每个元素出现的次数
    for num in arr:
        count[num] += 1
    # 计算每个元素应该放置的位置
    for i in range(1, count_len):
        count[i] += count[i-1]
    # 创建输出数组并排序
    output =  * len(arr)
    for num in arr:
        output[count[num]-1] = num
        count[num] -= 1
    return output

上述代码中，我们首先确定输入数组中的最大值，并根据最大值创建一个计数数组，长度为最大值加一。然后统计输入数组中每个元素出现的次数，并将计数结果存入计数数组。接下来，我们通过累加计数数组中的元素，计算每个元素应该放置的位置。最后，我们根据计数数组中的计数值和位置信息，将输入数组中的元素排序并输出。

使用计数排序算法对整数数组进行排序的时间复杂度为O(n+k)，空间复杂度为O(n)。在Python中实现计数排序算法时，需要占用一定的额外空间来存储计数数组和输出数组。但是，计数排序算法的稳定性较好，适用于整数数组的排序。在实际应用中，需要根据具体的数据规模和分布情况选择合适的排序算法。