博客

使用python实现希尔、计数、基数基础排序的代码

  • Post category:Python

下面是详细讲解“使用Python实现希尔、计数、基数基础排序的代码”的完整攻略。

1. 什么排序算法？

排序算法是一种将一组数据按照特定顺序排列的算法。排序算法可以按照复杂度、间复杂度、稳定性等方面进行分类。常见的排序算法包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序等。

2. Python实现希尔、计数、基数基础排序代码

2.1 希尔排序

希尔排序是一种基于插入排序的排序算法，它通过将数据分成多个子序列来进行排序。希尔排序的时间复杂度为O(nlogn)。

以下是Python实现希尔排序的代码：

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2
    return arr

2.2 计数排序

计数排序是一种非比较排序算法，它通过统计每个元素出现的次数来进行排序。计数排序的时间复杂度为O(n+k)，其中k为元素的范围。

以下是Python实现计数排序的代码：

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

2.3 基数排序

基数排序是一种非比较排序算法，它通过将数据按照位数进行排序。基数排序的时间复杂度为O(d(n+k))，其中d为最大位，k为元素的范围。

以下是Python实现基数排序的代码：

def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        count = [0] * 10
        for i in range(len(arr)):
            count[(arr[i] // exp) % 10] += 1
        for i in range(1, 10):
            count[i] += count[i - 1]
        output = [0] * len(arr)
        for i in range(len(arr) - 1, -1, -1):
            output[count[(arr[i] // exp) % 10] - 1] = arr[i]
            count[(arr[i] // exp) % 10] -= 1
        for i in range(len(arr)):
            arr[i] = output[i]
        exp *= 10
    return arr

2.4 示例说明

以下是两个示例说明，分别是使用希尔排序和计数排序进行排序。

2.4.1 希尔排序

以下是使用希尔排序进行排序的示例：

arr = [64, 25, 12, 22, 11]
sorted_arr = shell_sort(arr)
print(sorted_arr)

输出结果为：

[11, 12, 22, 25, 64]

.4.2 计数排序

以下是使用计数排序进行排序的示例：

arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print(sorted_arr)

输出结果为：

[1, 2, 2, 3, 3, 4, 8]

3. 总结

排序算法是一种将一组数据按照特定顺序排列算法。本文介绍了Python实现希尔、计数、基数基础排序的代码，包括希尔排序、计数排序和基数排序。同时，本文还提供了两个示例说明，分别是使用希尔排序和计数排序进行。

Tags: ,