Python 算法高级篇：归并排序的优化与外部排序

Python 算法高级篇：归并排序的优化与外部排序

引言

在计算机科学中，排序是一项基本的任务，而归并排序（ Merge Sort ）是一种著名的算法>排序算法，它具有稳定性和良好的时间复杂度。本文将介绍归并排序的基本原理，然后深入探讨如何进行优化以及如何应用归并排序进行外部排序。

😃😄 ❤️ ❤️ ❤️

1. 归并排序的基本原理

归并排序采用分治的策略，将一个大问题分解为小问题，解决小问题，然后将它们合并以获得最终解决方案。其基本步骤如下：

  • 1 . 分割（ Divide ）：将数组划分为两个子数组，通常是平均分割。
  • 2 . 递归（ Conquer ）：递归地对子数组进行排序。
  • 3 . 合并（ Merge ）：将排好序的子数组合并为一个有序的数组。

下面是一个简单的归并算法>排序算法的 Python 实现：

python">def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # 找到数组的中间位置
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)  # 递归排序左半部分
        merge_sort(right_half)  # 递归排序右半部分

        i = j = k = 0

        # 合并两个子数组
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

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

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

归并排序的时间复杂度是 O ( n log n )，它是一种稳定的算法>排序算法，但它需要额外的空间来存储临时数组。

2. 归并排序的优化

尽管归并排序的时间复杂度相对较低，但它在实际应用中可能会因为空间复杂度较高而受到限制。为了解决这个问题，可以进行一些优化。

2.1 自底向上的归并排序

传统的归并排序是自顶向下的，即从顶部开始递归划分子数组。在自底向上的归并排序中，我们从底部开始，首先将相邻的元素两两合并，然后是四四合并，八八合并，直到整个数组排序完成。这样可以减少递归所需的栈空间，降低空间复杂度。

以下是自底向上归并排序的 Python 实现：

python">def merge_sort_bottom_up(arr):
    n = len(arr)
    curr_size = 1

    while curr_size < n:
        for left in range(0, n - 1, 2 * curr_size):
            mid = min(left + curr_size - 1, n - 1)
            right = min(left + 2 * curr_size - 1, n - 1)

            if mid < right:
                merge(arr, left, mid, right)
        curr_size *= 2

def merge(arr, left, mid, right):
    n1 = mid - left + 1
    n2 = right - mid

    L = [0] * n1
    R = [0] * n2

    for i in range(n1):
        L[i] = arr[left + i]
    for i in range(n2):
        R[i] = arr[mid + i + 1]

    i = j = 0
    k = left

    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1

2.2 最后优化

归并排序的一个缺点是它需要额外的空间来存储临时数组。为了避免这种情况，可以使用一个额外的数组来存储一半的数据，然后交替地将数据复制到原始数组中。这可以降低空间复杂度，但增加了一些额外的复制操作。

以下是这种优化方法的 Python 实现：

python">def merge_sort_optimized(arr):
    n = len(arr)
    temp_arr = [0] * n

    curr_size = 1
    while curr_size < n:
        left = 0
        while left < n - 1:
            mid = min(left + curr_size - 1, n - 1)
            right = min(left + 2 * curr_size - 1, n - 1)
            if mid < right:
                merge_optimized(arr, left, mid, right, temp_arr)
            left += 2 * curr_size
        curr_size *= 2

def merge_optimized(arr, left, mid, right, temp_arr):
    i = left
    j = mid + 1
    for k in range(left, right + 1):
        temp_arr[k] = arr[k]
    k = left
    while i <= mid and j <= right:
        if temp_arr[i] <= temp_arr[j]:
            arr[k] = temp_arr[i]
            i += 1
        else:
            arr[k] = temp_arr[j]
            j += 1
        k += 1
    while i <= mid:
        arr[k] = temp_arr[i]
        k += 1
        i += 1

这种优化方法减少了内存的使用，但增加了一些额外的复制操作。

3. 外部排序

归并排序还可以应用于外部排序，这是一种处理大规模数据集的排序方法。外部排序的主要思想是将大数据集分成多个小数据块，每个小数据块都可以在内存中进行排序。排序后，将这些小数据块合并成一个有序的大数据集。

下面是一个简单的外部排序示例，假设我们有一个非常大的文件，无法一次性加载到内存中进行排序。我们可以将文件划分为多个小文件块，分别进行排序，然后合并它们。

python">def external_sort(input_file, output_file, chunk_size):
    # 划分文件为多个块
    divide_file(input_file, chunk_size)

    # 对每个块进行内部排序
    sort_chunks()

    # 合并排序后的块
    merge_sorted_chunks(output_file)

def divide_file(input_file, chunk_size):
    # 从输入文件中读取数据并划分为块
    pass

def sort_chunks():
    # 对每个块进行内部排序
    pass

def merge_sorted_chunks(output_file):
    # 合并排序后的块
    pass

这个示例演示了如何将大文件划分为多个小文件块，每个块都可以在内存中排序。然后，排序后的块将被合并为一个有序的输出文件。

4. 性能比较

为了演示归并排序的不同优化版本之间的性能差异，我们可以使用一些基准测试来比较它们的运行时间。下面是一个简单的性能比较示例：

python">import random
import timeit

arr = [random.randint(1, 1000) for _ in range(1000)]

# 未优化的归并排序
def merge_sort_original(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort_original(left_half)
        merge_sort_original(right_half)

        i = j = k = 0

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

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

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

# 测试未优化的归并排序的性能
original_time = timeit.timeit(lambda: merge_sort_original(arr.copy()), number=1000)

# 优化的归并排序
def merge_sort_optimized(arr):
    # 同上，省略优化后的代码

# 测试优化的归并排序的性能
optimized_time = timeit.timeit(lambda: merge_sort_optimized(arr.copy()), number=1000)

print("未优化的归并排序耗时：", original_time)
print("优化的归并排序耗时：", optimized_time)

在上述示例中，我们对未优化的归并排序和优化后的归并排序进行了性能测试。通过这种方式，你可以比较它们的性能并选择最适合你应用的版本。

5. 结论

归并排序是一种经典的算法>排序算法，它使用分治策略和合并操作，具有稳定的性质和较低的时间复杂度。通过进行优化，例如自底向上的归并排序和减少内存使用的外部排序，我们可以提高归并排序的性能和适用性。根据应用的需求和资源限制，选择合适的算法>排序算法版本，以获得最佳性能。这些优化方法可以在处理大数据集和内存受限的情况下发挥重要作用。

[ 专栏推荐 ]
😃 《Python 算法初阶：入门篇》😄
❤️【简介】：本课程是针对 Python 初学者设计的算法基础入门课程，涵盖算法概念、时间复杂度、空间复杂度等基础知识。通过实例演示线性搜索、二分搜索等算法，并介绍哈希表、深度优先搜索、广度优先搜索等搜索算法。此课程将为学员提供扎实的 Python 编程基础与算法入门，为解决实际问题打下坚实基础。
在这里插入图片描述


http://www.niftyadmin.cn/n/5129455.html

相关文章

代码随想录打卡第五十三天|309.最佳买卖股票时机含冷冻期 ● 714.买卖股票的最佳时机含手续费

代码随想录打卡第五十三天|309.最佳买卖股票时机含冷冻期 ● 714.买卖股票的最佳时机含手续费

309.最佳买卖股票时机含冷冻期 题目&#xff1a; 给定一个整数数组prices&#xff0c;其中第 prices[i] 表示第 i 天的股票价格 。​ 设计一个算法计算出最大利润。在满足以下约束条件下&#xff0c;你可以尽可能地完成更多的交易&#xff08;多次买卖一支股票&#xff09;: 卖…
阅读更多...
10G传输分析仪SDH表TFN D450S参数详情

10G传输分析仪SDH表TFN D450S参数详情

D450S 10G SDH系列 SDH/SONET传输测试模块 D450S系列SDH/SPNET传输测试模块是TFN模块化测试产品中的一款。D450S系列可配置在FT100测试平台上&#xff0c;实现广泛的PDH/DSn和SDH/SONET的测试功能&#xff0c;为城域网提供综合的测试方案&#xff0c;是高性价比的网络测试产品…
阅读更多...
【Python机器学习】零基础掌握GradientBoostingClassifier集成学习

【Python机器学习】零基础掌握GradientBoostingClassifier集成学习

什么能有效地解决分类问题，特别是在数据复杂、特征多样的情况下？ 面对这个问题，许多人可能会想到复杂的神经网络或深度学习方法。然而，有一种称为“梯度提升分类器”（Gradient Boosting Classifier）的算法，以其高准确度、灵活性和易用性赢得了大量用户的青睐。 假设在…
阅读更多...
2023CSP-J游寄

2023CSP-J游寄

没话说了&#xff0c;S组没进复赛&#xff0c;只能打J组&#xff0c;J组打的也是一团糟。。 过程 上午8:10 进考场了&#xff0c;打开vscode写模板 上午8:25 密码发下来了&#xff0c;开始解压&#xff0c;喝口水压压惊. 开始浏览题目&#xff0c;看到T3我又惊了&#xf…
阅读更多...
人生岁月年华

人生岁月年华

人生很长吗&#xff1f;不知道。只知道高中坐在教室里&#xff0c;闹哄哄的很难受。也记得上班时无聊敲着代码也很难受。 可是人生也不长。你没有太多时间去试错&#xff0c;你没有无限的时间精力去追寻你认为的高大上。 人生是何体验呢&#xff1f;人生的感觉很多吧。大多数…
阅读更多...
[论文笔记]GTE

[论文笔记]GTE

引言 今天带来今年的一篇文本嵌入论文GTE， 中文题目是 多阶段对比学习的通用文本嵌入。 作者提出了GTE，一个使用对阶段对比学习的通用文本嵌入。使用对比学习在多个来源的混合数据集上训练了一个统一的文本嵌入模型，通过在无监督预训练阶段和有监督微调阶段显著增加训练数…
阅读更多...
2023年中国背光显示面板分类、市场规模及企业分析[图]

2023年中国背光显示面板分类、市场规模及企业分析[图]

背光显示面板行业&#xff0c;指生产背光显示面板及其相关配件的制造商和供应商&#xff0c;这些制造商和供应商主要为电视机、电脑显示器、智能手机等电子产品提供背光显示面板及配件。背光显示面板是一种电子器件&#xff0c;其功能主要是将电信号转化为视觉图像&#xff0c;…
阅读更多...
Ansible上通过roles简化playbook演示介绍

Ansible上通过roles简化playbook演示介绍

目录 一.roles介绍 1.作用 2.role的目录结构 3.role和tasks的执行优先级顺序 二.自定义一个httpd的角色 1.完整目录结构展示 2.主要的各个目录配置 &#xff08;1&#xff09;vars目录和templates目录 &#xff08;2&#xff09;tasks目录和handlers目录 &#xff08…
阅读更多...
最新文章

Copyright @ 2022~2023