Python 基数排序

最后修改于 2025年3月8日

在本文中，我们将解释并在 Python 中实现基数排序算法。

算法 是解决问题或执行计算的分步过程。算法是计算机科学和编程的基础。

排序 是以特定顺序（例如升序或降序）排列数据的过程。排序对于高效的数据检索和分析至关重要。

常用排序算法

一些常见的排序算法包括

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

基数排序

基数排序是一种非比较型排序算法，它通过处理单个数字或字符来对数据进行排序。 它对于排序整数和字符串非常有效。

基数排序示例

以下示例演示了如何在 Python 中实现基数排序。

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

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

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

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

    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    max_num = max(arr)
    exp = 1
    while max_num // exp > 0:
        counting_sort(arr, exp)
        exp *= 10

arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print("Sorted array:", arr)

该示例使用基数排序对整数数组进行排序。 该算法从最低有效位到最高有效位处理数字。

$ ./radix_sort.py 
Sorted array: [2, 24, 45, 66, 75, 90, 170, 802]

对文本数据进行排序

基数排序也可用于对字符串进行排序。 以下示例按升序和降序对字符串列表进行排序。

def counting_sort_strings(arr, index):
    n = len(arr)
    output = [''] * n
    count = [0] * 256

    for s in arr:
        char = s[index] if index < len(s) else '\0'
        count[ord(char)] += 1

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

    i = n - 1
    while i >= 0:
        char = arr[i][index] if index < len(arr[i]) else '\0'
        output[count[ord(char)] - 1] = arr[i]
        count[ord(char)] -= 1
        i -= 1

    for i in range(n):
        arr[i] = output[i]

def radix_sort_strings(arr, reverse=False):
    max_len = max(len(s) for s in arr)
    for i in range(max_len - 1, -1, -1):
        counting_sort_strings(arr, i)
    if reverse:
        arr.reverse()

arr = ["apple", "banana", "kiwi", "mango", "cherry"]
radix_sort_strings(arr)
print("Sorted array (ascending):", arr)

radix_sort_strings(arr, reverse=True)
print("Sorted array (descending):", arr)

该示例使用基数排序对字符串列表进行排序。 该算法从最低有效位到最高有效位处理字符。

$ ./radix_sort_strings.py 
Sorted array (ascending): ['apple', 'banana', 'cherry', 'kiwi', 'mango']
Sorted array (descending): ['mango', 'kiwi', 'cherry', 'banana', 'apple']

基数排序与快速排序的比较

基数排序和快速排序都是高效的排序算法，但它们有不同的用例。 基数排序非常适合排序整数和字符串，而快速排序是一种通用的排序算法。

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

import time
import random

import time
import random

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

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

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

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

    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    max_num = max(arr)
    exp = 1
    while max_num // exp > 0:
        counting_sort(arr, exp)
        exp *= 10

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)

arr = [random.randint(0, 10000) for _ in range(10000)]

start = time.time()
radix_sort(arr.copy())
end = time.time()
print("Radix Sort time:", end - start)

start = time.time()
quick_sort(arr.copy())
end = time.time()
print("Quick Sort time:", end - start)

该示例在大型随机整数数组上对基数排序和快速排序进行基准测试。

来源

维基百科上的基数排序

在本文中，我们已经实现并解释了 Python 中的基数排序算法。

作者

我的名字是 Jan Bodnar，我是一位充满热情的程序员，拥有丰富的编程经验。 我自 2007 年以来一直撰写编程文章。 迄今为止，我已经撰写了 1,400 多篇文章和 8 本电子书。 我拥有超过十年的编程教学经验。

列出所有 Python 教程。