Python 计数排序算法

最后修改于 2025年3月8日

在本文中，我们将介绍 Python 中的计数排序算法。我们将涵盖基本定义，提供对数值和文本数据进行排序的示例，并将计数排序与快速排序进行比较。

算法是解决问题或执行计算的逐步过程。算法是计算机程序的主干。

排序 是按特定顺序（例如升序或降序）排列数据的过程。排序是计算机科学中的一项基本操作。

常用排序算法

一些常见的排序算法包括

• 气泡排序
• 选择排序
• 插入排序
• 归并排序
• 快速排序
• 计数排序

计数排序算法

计数排序是一种非基于比较的排序算法。它通过计算输入列表中每个元素出现的次数，并使用算术运算来确定元素在排序输出中的位置。

计数排序示例

以下是计数排序算法的 Python 实现。

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)
    
    for num in arr:
        count[num] += 1
    
    sorted_arr = []
    for i in range(len(count)):
        sorted_arr.extend([i] * count[i])
    
    return sorted_arr

# Example usage
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print("Sorted array:", sorted_arr)

该示例使用计数排序按升序对整数列表进行排序。

$ ./counting_sort.py 
Sorted array: [1, 2, 2, 3, 3, 4, 8]

对文本数据进行排序

计数排序也可用于对文本数据进行排序。这是一个例子

def counting_sort_text(arr):
    max_val = ord(max(arr))
    count = [0] * (max_val + 1)
    
    for char in arr:
        count[ord(char)] += 1
    
    sorted_arr = []
    for i in range(len(count)):
        sorted_arr.extend([chr(i)] * count[i])
    
    return sorted_arr

# Example usage
text = "counting"
sorted_text = counting_sort_text(text)
print("Sorted text:", ''.join(sorted_text))

该示例使用计数排序按升序对字符串进行排序。

$ ./counting_sort_text.py 
Sorted text: cginnottu

降序排序

要按降序排序，我们可以修改计数排序算法。

def counting_sort_desc(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)
    
    for num in arr:
        count[num] += 1
    
    sorted_arr = []
    for i in range(len(count) - 1, -1, -1):
        sorted_arr.extend([i] * count[i])
    
    return sorted_arr

# Example usage
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort_desc(arr)
print("Sorted array (descending):", sorted_arr)

该示例按降序对整数列表进行排序。

$ ./counting_sort_desc.py 
Sorted array (descending): [8, 4, 3, 3, 2, 2, 1]

与快速排序的比较

计数排序对于小范围的整数是有效的，但也有局限性。快速排序是一种基于比较的算法，适用于更大的数据集。

基准测试示例

以下示例比较了计数排序和快速排序的性能。

import time
import random

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)
    
    for num in arr:
        count[num] += 1
    
    sorted_arr = []
    for i in range(len(count)):
        sorted_arr.extend([i] * count[i])
    
    return sorted_arr

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

# Generate a large dataset
data = [random.randint(0, 1000) for _ in range(10000)]

# Benchmark counting sort
start_time = time.time()
counting_sort(data)
counting_time = time.time() - start_time

# Benchmark quick sort
start_time = time.time()
quick_sort(data)
quick_time = time.time() - start_time

print(f"Counting sort time: {counting_time:.6f} seconds")
print(f"Quick sort time: {quick_time:.6f} seconds")

该示例对大型数据集上的计数排序和快速排序进行基准测试。

计数排序是一种简单有效的算法，适用于对小范围内的整数进行排序。但是，对于较大的数据集，像快速排序这样基于比较的算法更合适。

作者

我叫 Jan Bodnar，我是一位充满热情的程序员，拥有丰富的编程经验。我从 2007 年开始撰写编程文章。到目前为止，我已经撰写了 1,400 多篇文章和 8 本电子书。我拥有超过十年的编程教学经验。

列出所有 Python 教程。