ITPub博客
首页 博客 专栏 学院 社区 IT新媒体评选
发博

首页 > 应用开发 > Python > Python 如何实现快速排序和归并排序？

Python 如何实现快速排序和归并排序？

原创 Python 作者：mingtian66 时间：2024-11-10 12:53:20 0 删除 编辑

在 Python 中，可以使用递归的方法来实现快速排序和归并排序。以下是它们的实现方式：
快速排序（Quicksort）

快速排序是一种分治排序算法，通过选择一个“基准”（pivot）元素，然后将数组分为小于和大于该基准的两部分，递归地对这两部分进行排序。

def quicksort(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 quicksort(left) + middle + quicksort(right)

使用示例：

arr = [3, 6, 8, 10, 1, 2, 1]
print(quicksort(arr))  # 输出：[1, 1, 2, 3, 6, 8, 10]

归并排序（Merge Sort）

归并排序也是一种分治排序算法。它将数组分成两个部分，分别对这两个部分排序，然后合并排序好的部分。

def merge_sort(arr):
    # 基础情况：如果数组为空或只有一个元素，则不需要排序
    if len(arr) <= 1:
        return arr

    # 分割数组
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    # 递归排序左右部分并合并
    return merge(merge_sort(left), merge_sort(right))

def merge(left, right):
    result = []
    i = j = 0

    # 合并两个排序数组
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # 添加剩余元素
    result.extend(left[i:])
    result.extend(right[j:])

    return result

使用示例：

arr = [3, 6, 8, 10, 1, 2, 1]
print(merge_sort(arr))  # 输出：[1, 1, 2, 3, 6, 8, 10]

这两种排序方法的时间复杂度都为 O(nlog⁡n)O(nlogn)

来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/70040412/viewspace-3048243/ ，如需转载，请注明出处，否则将追究法律责任。

0
0
上一篇： 如何在 Java 中创建一个工厂类？
下一篇： 如何在 Python 中实现二分查找？
请登录后发表评论 登录
全部评论
mingtian66

注册时间：2024-08-07

  • 博文量
    589
  • 访问量
    603014

最新文章

支持我们 作者招募 用户协议 FAQ Contact Us

北京盛拓优讯信息技术有限公司. 版权所有  京ICP备16024965号-8 北京市公安局海淀分局网监中心备案编号：11010802021510 niuxiaotong@pcpop.com 17352615567 未成年人举报专区

广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员

违法和不良信息举报电话:18101376593