数据结构与算法-归并排序

简介: 数据结构与算法-归并排序

归并排序:

       归并排序是一种分治算法,它的原理是将待排序的数组不断分割成更小的子数组,直到每个子数组只有一个元素为止,然后将这些子数组按照大小顺序合并起来,最终得到一个有序的数组。

具体步骤如下:

  1. 将待排序的数组分成两个子数组,然后分别对这两个子数组进行归并排序。
  2. 将两个已经排序好的子数组合并成一个有序的数组。这里需要一个额外的数组来存放合并后的结果。
  3. 重复以上步骤,直到所有的子数组都合并成一个完整的有序数组。

代码实现:

n=int(input())  #要排序的数组的长度
ls=list(map(int,input().split())) # 输入要排序的数组
def MergeSort(ls):
    if len(ls)<=1:
        return ls
    mid = int(len(ls)/2)  # 对原列表进行分治
    llist,rlist=MergeSort(ls[:mid]),MergeSort(ls[mid:]) #再次分治调用自身 缩短要排序的长度
    result=[]
    i,j=0,0
    while  i<len(llist) and j<len(rlist):
        if rlist[j]<llist[i]:
            result.append(rlist[j])
            j+=1
        else:
            result.append(llist[i])
            i+=1
    result += llist[i:]+rlist[j:]
    return result
for j in MergeSort(ls): #输出结果
    print(j,end=' ')

复杂度:

       归并排序是一种稳定的排序算法,时间复杂度为O(nlogn),空间复杂度为O(n)。它的主要优点是可以对链表等非随机访问的数据结构进行排序,并且在最坏情况下的时间复杂度也是O(nlogn)。

目录
打赏
0
2
2
0
37
分享
相关文章
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
【C++数据结构——内排序】二路归并排序(头歌实践教学平台习题)【合集】
本关任务是实现二路归并算法,即将两个有序数组合并为一个有序数组。主要内容包括: - **任务描述**:实现二路归并算法。 - **相关知识**: - 二路归并算法的基本概念。 - 算法步骤:通过比较两个有序数组的元素,依次将较小的元素放入新数组中。 - 代码示例(以 C++ 为例)。 - 时间复杂度为 O(m+n),空间复杂度为 O(m+n)。 - **测试说明**:平台会对你编写的代码进行测试,提供输入和输出示例。 - **通关代码**:提供了完整的 C++ 实现代码。 - **测试结果**:展示代码运行后的排序结果。 开始你的任务吧,祝你成功!
38 10
【初阶数据结构篇】归并排序和计数排序(总结篇)
归并排序(MERGE-SORT)是建⽴在归并操作上的⼀种有效的排序算法,该算法是采⽤分治法(Divide andConquer)的⼀个⾮常典型的应⽤。
79 0
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
84 1
|
4月前
【初阶数据结构】打破递归束缚:掌握非递归版快速排序与归并排序
【初阶数据结构】打破递归束缚:掌握非递归版快速排序与归并排序
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
102 0
|
4月前
|
深入了解归并排序算法
深入了解归并排序算法
65 0
算法实战:手写归并排序,让复杂排序变简单!
归并排序是一种基于“分治法”的经典算法,通过递归分割和合并数组,实现O(n log n)的高效排序。本文将通过Java手写代码,详细讲解归并排序的原理及实现,帮助你快速掌握这一实用算法。
63 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等