Python 算法基础篇：归并排序和快速排序

小蓝枣

发布于 2023-07-24 15:12:26

7300

文章被收录于专栏：CSDN博客专家-小蓝枣的博客CSDN博客专家-小蓝枣的博客

Python 算法基础篇：归并排序和快速排序

引言

归并排序和快速排序是两种高效的排序算法，用于将一个无序列表按照特定顺序重新排列。本篇博客将介绍归并排序和快速排序的基本原理，并通过实例代码演示它们的应用。

😃😄 ❤️ ❤️ ❤️

1. 归并排序算法概述

归并排序是一种分治法排序算法，它将列表分成两个子列表，分别进行排序，然后将两个有序子列表合并为一个有序列表。归并排序的核心思想是分而治之，将问题分解为较小的子问题，解决子问题后再合并结果。

归并排序的主要优点是稳定且效率高，时间复杂度为 O ( n log n )，适用于处理大规模数据的排序。

2. 归并排序算法实现

实例1：归并排序

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    # 分解列表为两个子列表
    middle = len(arr) // 2
    left = arr[:middle]
    right = arr[middle:]

    # 递归对子列表进行排序
    left = merge_sort(left)
    right = merge_sort(right)

    # 合并两个有序子列表
    return merge(left, right)

def merge(left, right):
    result = []
    left_idx, right_idx = 0, 0

    # 比较并合并两个子列表
    while left_idx < len(left) and right_idx < len(right):
        if left[left_idx] < right[right_idx]:
            result.append(left[left_idx])
            left_idx += 1
        else:
            result.append(right[right_idx])
            right_idx += 1

    # 将剩余的元素添加到结果列表中
    result += left[left_idx:]
    result += right[right_idx:]

    return result

# 测试归并排序
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = merge_sort(arr)
print("归并排序结果：", sorted_arr)

代码解释：上述代码演示了使用归并排序对一个列表进行排序的实例。归并排序是一种分治法算法，它将列表分解为两个子列表，然后递归地对子列表进行排序。最后，通过 merge 函数将两个有序子列表合并为一个有序列表。

3. 快速排序算法概述

快速排序是一种分治法排序算法，它选择一个基准元素，并将列表分成两个子列表，一个子列表的元素都小于基准元素，另一个子列表的元素都大于基准元素。然后递归地对两个子列表进行排序，最后将它们合并起来。

快速排序的核心思想是每次通过划分操作将问题规模缩小，排序过程中不需要额外的存储空间，时间复杂度为 O ( n log n )，适用于处理大规模数据的排序。

4. 快速排序算法实现

实例2：快速排序

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 = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = quick_sort(arr)
print("快速排序结果：", sorted_arr)

代码解释：上述代码演示了使用快速排序对一个列表进行排序的实例。快速排序选择一个基准元素，然后将列表分成三个子列表：小于基准元素的左子列表、等于基准元素的中间子列表和大于基准元素的右子列表。接着，通过递归地对子列表进行排序，最后将它们合并起来。