counting sort python

计数排序是一种非比较排序算法，它的时间复杂度为O(n+k)，其中n是待排序元素的个数，k是待排序元素中最大值和最小值的差值加1。在Python中，可以使用以下代码实现计数排序：

def counting_sort(arr):
# 找到最大值和最小值
max_val = max(arr)
min_val = min(arr)
# 初始化计数数组
count_arr = [] * (max_val - min_val + 1)
# 统计每个元素出现的次数
for i in arr:
count_arr[i - min_val] += 1
# 对计数数组进行前缀和操作
for i in range(1, len(count_arr)):
count_arr[i] += count_arr[i - 1]
# 初始化排序后的数组
sorted_arr = [] * len(arr)
# 从后往前遍历原数组，将元素放入排序后的数组中
for i in range(len(arr) - 1, -1, -1):
sorted_arr[count_arr[arr[i] - min_val] - 1] = arr[i]
count_arr[arr[i] - min_val] -= 1
return sorted_arr

相关问题

python sort 时间复杂度

Python的排序算法的时间复杂度可以根据具体的实现方式有所不同。下面是几种常见的排序算法及其时间复杂度：

1. 冒泡排序（Bubble Sort）：最坏情况下的时间复杂度为O(n^2)，平均情况下的时间复杂度也为O(n^2)。

2. 选择排序（Selection Sort）：最坏情况下的时间复杂度为O(n^2)，平均情况下的时间复杂度也为O(n^2)。

3. 插入排序（Insertion Sort）：最坏情况下的时间复杂度为O(n^2)，平均情况下的时间复杂度也为O(n^2)。

4. 快速排序（Quick Sort）：最坏情况下的时间复杂度为O(n^2)，平均情况下的时间复杂度为O(nlogn)。

5. 归并排序（Merge Sort）：最坏情况下的时间复杂度为O(nlogn)，平均情况下的时间复杂度也为O(nlogn)。

6. 堆排序（Heap Sort）：最坏情况下的时间复杂度为O(nlogn)，平均情况下的时间复杂度也为O(nlogn)。

7. 希尔排序（Shell Sort）：最坏情况下的时间复杂度取决于增量序列的选择，平均情况下的时间复杂度为O(n^1.3)。

8. 计数排序（Counting Sort）：时间复杂度为O(n+k)，其中k是待排序数组中的最大值。

9. 桶排序（Bucket Sort）：时间复杂度为O(n+k)，其中k是桶的数量。

10. 基数排序（Radix Sort）：时间复杂度为O(d(n+k))，其中d是数字的位数，k是每个位数可能的取值范围。

需要注意的是，这些排序算法的时间复杂度都是基于比较的排序算法。非基于比较的排序算法，例如计数排序、桶排序和基数排序，可以在特定情况下达到线性时间复杂度。

Python排序算法

以下是两种常见的Python排序算法的介绍和示例：

1. 计数排序：
计数排序是一种不基于比较的排序算法，它的速度更快。但是它需要额外的空间来存放排序后的数列。
算法描述：
- 首先，找出待排序数组中的最大值和最小值。
- 创建一个计数数组，长度为最大值和最小值之间的差值加一。
- 遍历待排序数组，将每个元素的计数值加一。
- 遍历计数数组，将每个元素与前一个元素相加，得到每个元素在排序后数组中的位置。
- 创建一个与待排序数组相同长度的结果数组。
- 遍历待排序数组，将每个元素放入结果数组的对应位置，并将计数数组中对应元素的值减一。
- 返回结果数组作为排序后的数组。

示例代码：

def counting_sort(arr):
    min_val = min(arr)
    max_val = max(arr)
    count = [0] * (max_val - min_val + 1)
    for num in arr:
        count[num - min_val] += 1
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    result = [0] * len(arr)
    for num in arr:
        result[count[num - min_val] - 1] = num
        count[num - min_val] -= 1
    return result

2. 选择排序：
选择排序是一种简单但不稳定的排序算法，时间复杂度为O(n^2)，适用于小数据。
算法描述：
- 首先，将数组分成已排序和未排序两组。
- 遍历未排序数组，从中找出最小值的索引。
- 将最小值与未排序数组的首位元素交换位置。
- 重复上述步骤，直到未排序数组为空。

示例代码：

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[min_index], arr[i] = arr[i], arr[min_index]
    return arr