计数排序 - 元素码农

发布时间: 2025-03-21 18:43

↑

# 计数排序

计数排序（Counting Sort）是一种非比较性的排序算法，它的核心思想是统计每个元素出现的次数，然后根据统计结果将元素放置到正确的位置。这种算法特别适用于整数排序，尤其是当待排序的数据范围不是很大的情况。

## 基本原理

1. 找出待排序数组中的最大值和最小值
2. 创建计数数组，统计每个元素出现的次数
3. 根据计数数组计算每个元素的最终位置
4. 创建结果数组，将元素放到正确的位置

## 动画演示

```
原始数组：[ 4 2 2 8 3 3 1 ]

统计频次：
索引：  0 1 2 3 4 5 6 7 8
频次：  0 1 2 2 1 0 0 0 1

计算位置：
索引：  0 1 2 3 4 5 6 7 8
位置：  0 1 3 5 6 6 6 6 7

结果数组：[ 1 2 2 3 3 4 8 ]
```

## 代码实现

### 基本实现

```python
def counting_sort(arr):
    if not arr:
        return arr
    
    # 找出数组的最大值和最小值
    max_val = max(arr)
    min_val = min(arr)
    
    # 计算计数数组的大小
    range_val = max_val - min_val + 1
    
    # 创建计数数组并统计每个元素出现的次数
    count = [0] * range_val
    for num in arr:
        count[num - min_val] += 1
    
    # 重建排序后的数组
    sorted_arr = []
    for i in range(range_val):
        sorted_arr.extend([i + min_val] * count[i])
    
    return sorted_arr

# 使用示例
arr = [4, 2, 2, 8, 3, 3, 1]
print("排序前:", arr)
sorted_arr = counting_sort(arr)
print("排序后:", sorted_arr)
```

### 稳定版本

```python
def stable_counting_sort(arr):
    if not arr:
        return arr
    
    # 找出数组的最大值和最小值
    max_val = max(arr)
    min_val = min(arr)
    
    # 计算计数数组的大小
    range_val = max_val - min_val + 1
    
    # 创建计数数组并统计每个元素出现的次数
    count = [0] * range_val
    for num in arr:
        count[num - min_val] += 1
    
    # 修改计数数组，使其包含每个元素的结束位置
    for i in range(1, range_val):
        count[i] += count[i - 1]
    
    # 创建结果数组
    result = [0] * len(arr)
    
    # 从后向前遍历原数组，保持稳定性
    for num in reversed(arr):
        index = count[num - min_val] - 1
        result[index] = num
        count[num - min_val] -= 1
    
    return result

# 使用示例
arr = [4, 2, 2, 8, 3, 3, 1]
print("排序前:", arr)
sorted_arr = stable_counting_sort(arr)
print("排序后:", sorted_arr)
```

### 对象排序版本

```python
def counting_sort_objects(arr, key_func):
    if not arr:
        return arr
    
    # 获取所有对象的键值
    keys = [key_func(item) for item in arr]
    
    # 找出键值的范围
    max_key = max(keys)
    min_key = min(keys)
    range_key = max_key - min_key + 1
    
    # 创建计数数组
    count = [0] * range_key
    for key in keys:
        count[key - min_key] += 1
    
    # 计算位置
    for i in range(1, range_key):
        count[i] += count[i - 1]
    
    # 创建结果数组
    result = [None] * len(arr)
    
    # 从后向前遍历，保持稳定性
    for i in range(len(arr) - 1, -1, -1):
        key = key_func(arr[i])
        index = count[key - min_key] - 1
        result[index] = arr[i]
        count[key - min_key] -= 1
    
    return result

# 使用示例
class Student:
    def __init__(self, name, score):
        self.name = name
        self.score = score
    
    def __str__(self):
        return f"{self.name}: {self.score}"

students = [
    Student("Alice", 85),
    Student("Bob", 92),
    Student("Charlie", 85),
    Student("David", 78),
    Student("Eve", 92)
]

print("排序前:")
for student in students:
    print(student)

# 按分数排序
sorted_students = counting_sort_objects(students, lambda x: x.score)

print("\n按分数排序后:")
for student in sorted_students:
    print(student)
```

## 性能分析

### 时间复杂度

- 最好情况：O(n + k)
- 最坏情况：O(n + k)
- 平均情况：O(n + k)

其中：
- n 是待排序数组的长度
- k 是整数的范围（最大值-最小值+1）

### 空间复杂度

- O(k)，需要额外的计数数组
- 如果要求稳定排序，还需要O(n)的结果数组

### 稳定性

- 基本实现：不稳定
- 改进版本：稳定

## 优缺点

### 优点

1. 时间复杂度为线性
2. 适合整数排序
3. 可以实现稳定排序
4. 适合范围集中的数据

### 缺点

1. 只适用于整数或可以转换为整数的数据
2. 当数据范围很大时，空间消耗大
3. 需要知道数据范围

## 应用场景

1. 整数排序
2. 范围有限的数据排序
3. 年龄、分数等数值统计
4. 基数排序的中间步骤

## 实际应用示例

### 1. 成绩分布统计

```python
class ScoreAnalyzer:
    def __init__(self):
        self.scores = []
    
    def add_score(self, score):
        self.scores.append(score)
    
    def analyze_distribution(self):
        if not self.scores:
            return {}
        
        # 假设分数范围是0-100
        count = [0] * 101
        for score in self.scores:
            count[score] += 1
        
        # 统计分数分布
        distribution = {}
        ranges = [(0, 59), (60, 69), (70, 79), (80, 89), (90, 100)]
        labels = ["不及格", "及格", "良好", "优秀", "优秀+"]
        
        for (start, end), label in zip(ranges, labels):
            count_range = sum(count[start:end+1])
            percentage = count_range / len(self.scores) * 100
            distribution[label] = {
                "count": count_range,
                "percentage": f"{percentage:.2f}%"
            }
        
        return distribution

# 使用示例
analyzer = ScoreAnalyzer()
scores = [85, 92, 78, 64, 88, 95, 73, 89, 59, 91]
for score in scores:
    analyzer.add_score(score)

print("成绩分布情况:")
for category, stats in analyzer.analyze_distribution().items():
    print(f"{category}: {stats['count']}人 ({stats['percentage']})")
```

### 2. 年龄分组

```python
class AgeGrouper:
    def __init__(self):
        self.people = []
    
    def add_person(self, name, age):
        self.people.append({"name": name, "age": age})
    
    def group_by_age(self):
        if not self.people:
            return []
        
        # 找出年龄范围
        ages = [person["age"] for person in self.people]
        min_age = min(ages)
        max_age = max(ages)
        
        # 创建计数数组
        count = [0] * (max_age - min_age + 1)
        for age in ages:
            count[age - min_age] += 1
        
        # 计算位置
        for i in range(1, len(count)):
            count[i] += count[i - 1]
        
        # 创建结果数组
        result = [None] * len(self.people)
        for person in reversed(self.people):
            age = person["age"]
            index = count[age - min_age] - 1
            result[index] = person
            count[age - min_age] -= 1
        
        return result

# 使用示例
grouper = AgeGrouper()
people_data = [
    ("Alice", 25),
    ("Bob", 30),
    ("Charlie", 25),
    ("David", 35),
    ("Eve", 30)
]

for name, age in people_data:
    grouper.add_person(name, age)

print("按年龄分组结果:")
grouped = grouper.group_by_age()
for person in grouped:
    print(f"{person['name']}: {person['age']}岁")
```

## 总结

计数排序是一种特殊的排序算法，它具有以下特点：

1. 非比较性排序算法
2. 时间复杂度为线性O(n + k)
3. 适用于整数或可转换为整数的数据
4. 当数据范围较小时效率很高

在实际应用中，计数排序常用于：
- 整数数据的排序
- 数据统计和分析
- 作为基数排序的辅助步骤

虽然计数排序有其局限性（只适用于整数、需要额外空间），但在适合的场景下，它是一个非常高效的排序算法。通过合理的优化和改进，计数排序可以满足不同的需求，如保持稳定性或处理对象排序等。