怎样在Python中实现排序算法？-Python教程-PHP中文网

怎样在Python中实现排序算法？

下次还敢

发布： 2025-04-30 08:15:01

原创

837人浏览过

python中实现排序算法的方法包括冒泡排序、快速排序和归并排序。1. 冒泡排序适用于小数据集，时间复杂度为o(n^2)。2. 快速排序平均时间复杂度为o(n log n)，但在最坏情况下可能退化为o(n^2)。3. 归并排序时间复杂度为o(n log n)，稳定但需要额外空间。

怎样在Python中实现排序算法？

在Python中实现排序算法是一项既有趣又有挑战性的任务。让我们从回答这个问题开始，然后深入探讨如何在Python中实现各种排序算法。

Python中实现排序算法的方法有很多，从简单的冒泡排序到更复杂的高级算法如快速排序和归并排序。Python的标准库中已经提供了sort()和sorted()函数，它们内部使用了高效的Timsort算法，但如果你想自己实现这些算法，不仅能更好地理解排序的原理，还能根据具体需求进行优化。

让我们从一个简单的冒泡排序开始吧。冒泡排序虽然效率不高，但在小数据集上仍然是一个很好的学习工具。

立即学习“Python免费学习笔记（深入）”；

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# 示例使用
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = bubble_sort(numbers)
print(sorted_numbers)  # 输出: [11, 12, 22, 25, 34, 64, 90]

登录后复制

冒泡排序的实现非常直观，但它的时间复杂度是O(n^2)，在处理大数据集时效率低下。让我们再看看快速排序，这是一个更高效的算法，平均时间复杂度为O(n log n)。

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        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)

# 示例使用
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = quick_sort(numbers)
print(sorted_numbers)  # 输出: [11, 12, 22, 25, 34, 64, 90]

登录后复制

快速排序的实现利用了分治的思想，通过选择一个pivot（基准值）将数组分成三部分：小于pivot的部分，等于pivot的部分，以及大于pivot的部分。这种方法在大多数情况下都非常高效，但需要注意的是，在最坏情况下（例如数组已经是有序的），它的时间复杂度会退化到O(n^2)。

算家云

高效、便捷的人工智能算力服务平台

查看详情

再来看看归并排序，这也是一个基于分治思想的排序算法，时间复杂度为O(n log n)，并且在任何情况下都不会退化。

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

# 示例使用
numbers = [64, 34, 25, 12, 22, 11, 90]
merge_sort(numbers)
print(numbers)  # 输出: [11, 12, 22, 25, 34, 64, 90]

登录后复制

归并排序的实现需要额外的空间来存储临时数组，这一点需要注意。在实际应用中，选择哪种排序算法取决于数据集的大小、是否已经部分有序，以及对空间和时间的要求。

在实现这些排序算法时，我发现了一些有趣的经验和踩坑点：