【数据结构与算法】归并排序的原理及算法实现

简介: 【数据结构与算法】归并排序的原理及算法实现

归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组,再合并数组

将数组分解到最小之后,合并两个有序的数组,基本思路就是比较两个数组最前面的数字,谁小就先取谁,取了后相应的指针就往后移动一位。然后再比较,知道一个数组为空,最后把一个数组的剩余部分复制过来即可

文章目录

image.png2.左右继续拆分到每一个子部分只有一个元素,如下,拆分到只有一个子元素的之后拆分结束image.png3,拆分完之后进行合并,56跟26是上面绿色框拆出来的,合并的时候采用小的在前,大的在后。image.png4.把两个绿色块进行合并,这个时候就要借助定义的游标了,一个指的是左边大部分Left ,一个是右边的Right.合并的时候采用的方式是,对于左边的部分有一个游标,右边的部分也有一个游标,然后对于所指的两个部分进行比较换位。image.png5.经过比较17比较小,拿出来,之后Right向后移动一位。image.png6.之后继续比较Right的指向比26大,取出26,Left继续向后移动一位。之后比较发现Right指向比Left大,取出54,最后把Right放到后面,得到下面的一个有序数列。image.png7.右边继续采用相同的方式,的得到两个部分,之后现在对于整个序列来说就只有两个部分了。image.png8.按照上面相同的方式对两个绿色框的数据进行合并。依旧是左边的游标Left,右边的右边Right对比。得到了一个有序的数列image.png

这个就是归并算法的思想:把一组元素一直拆分到只有一个子元素,之后开始合并,通过Left与Right进行排序。

那么对于奇数个也是一样的,只不过拆分的时候最后的的一组多出来一个。合并的时候也是,先把最后那个灰色框那两个合并到一起,再跟44合并成3个,怎么拆的就怎么合并。

image.png归并算法代码实现

'''

Create by YO

@Time:  2020/4/22

'''


#相除的时候两个斜杠无小数部分。向下取整

def merge_sort(alist):

   '''归并排序'''

   n=len(alist)

   if n<=1:

       return alist

   mid=n//2    #中间值

   left_li=merge_sort(alist[:mid])

   #right   采用归并排序后形成的新的列表

   right_li=merge_sort(alist[mid:])

   #将两个有序的子序列合并成一个新的整体  merge(left,right)  左边的指针跟右边的指针都指向两个子序列的第一个元素

   left_pointer,right_pointer=0,0

   result=[]


   while left_pointer<len(left_li) and right_pointer<len(right_li):

       if left_li[left_pointer]<right_li[right_pointer]:

           result.append(left_li[left_pointer])

           left_pointer+=1   #移动完向后一位移动

       else:

         result.append(right_li[right_pointer])

         right_pointer+=1

   result+=left_li[left_pointer:]

   result+=right_li[right_pointer:]

   return result




if __name__ == "__main__":

   li = [54, 26, 93, 17, 77, 31, 44, 55, 20]

   print(li)

   sorted_li=merge_sort(li)

   print(li)

   print(sorted_li)


输出:

[54, 26, 93, 17, 77, 31, 44, 55, 20]

[54, 26, 93, 17, 77, 31, 44, 55, 20]

[17, 20, 26, 31, 44, 54, 55, 77, 93]

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42


image.png

目录
打赏
0
0
0
0
10
分享
相关文章
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
68 1
深度强化学习中SAC算法:数学原理、网络架构及其PyTorch实现
软演员-评论家算法(Soft Actor-Critic, SAC)是深度强化学习领域的重要进展,基于最大熵框架优化策略,在探索与利用之间实现动态平衡。SAC通过双Q网络设计和自适应温度参数,提升了训练稳定性和样本效率。本文详细解析了SAC的数学原理、网络架构及PyTorch实现,涵盖演员网络的动作采样与对数概率计算、评论家网络的Q值估计及其损失函数,并介绍了完整的SAC智能体实现流程。SAC在连续动作空间中表现出色,具有高样本效率和稳定的训练过程,适合实际应用场景。
66 7
深度强化学习中SAC算法:数学原理、网络架构及其PyTorch实现
【C++数据结构——内排序】二路归并排序(头歌实践教学平台习题)【合集】
本关任务是实现二路归并算法,即将两个有序数组合并为一个有序数组。主要内容包括: - **任务描述**:实现二路归并算法。 - **相关知识**: - 二路归并算法的基本概念。 - 算法步骤:通过比较两个有序数组的元素,依次将较小的元素放入新数组中。 - 代码示例(以 C++ 为例)。 - 时间复杂度为 O(m+n),空间复杂度为 O(m+n)。 - **测试说明**:平台会对你编写的代码进行测试,提供输入和输出示例。 - **通关代码**:提供了完整的 C++ 实现代码。 - **测试结果**:展示代码运行后的排序结果。 开始你的任务吧,祝你成功!
29 10
理解CAS算法原理
CAS(Compare and Swap,比较并交换)是一种无锁算法,用于实现多线程环境下的原子操作。它通过比较内存中的值与预期值是否相同来决定是否进行更新。JDK 5引入了基于CAS的乐观锁机制,替代了传统的synchronized独占锁,提升了并发性能。然而,CAS存在ABA问题、循环时间长开销大和只能保证单个共享变量原子性等缺点。为解决这些问题,可以使用版本号机制、合并多个变量或引入pause指令优化CPU执行效率。CAS广泛应用于JDK的原子类中,如AtomicInteger.incrementAndGet(),利用底层Unsafe库实现高效的无锁自增操作。
理解CAS算法原理
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
34 2
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
2月前
|
数据结构之路由表查找算法(深度优先搜索和宽度优先搜索)
在网络通信中,路由表用于指导数据包的传输路径。本文介绍了两种常用的路由表查找算法——深度优先算法(DFS)和宽度优先算法(BFS)。DFS使用栈实现,适合路径问题;BFS使用队列,保证找到最短路径。两者均能有效查找路由信息,但适用场景不同,需根据具体需求选择。文中还提供了这两种算法的核心代码及测试结果,验证了算法的有效性。
131 23
|
2月前
|
数据结构之蜜蜂算法
蜜蜂算法是一种受蜜蜂觅食行为启发的优化算法,通过模拟蜜蜂的群体智能来解决优化问题。本文介绍了蜜蜂算法的基本原理、数据结构设计、核心代码实现及算法优缺点。算法通过迭代更新蜜蜂位置,逐步优化适应度,最终找到问题的最优解。代码实现了单链表结构,用于管理蜜蜂节点,并通过适应度计算、节点移动等操作实现算法的核心功能。蜜蜂算法具有全局寻优能力强、参数设置简单等优点,但也存在对初始化参数敏感、计算复杂度高等缺点。
73 20
【AI系统】布局转换原理与算法
数据布局转换技术通过优化内存中数据的排布,提升程序执行效率,特别是对于缓存性能的影响显著。本文介绍了数据在内存中的排布方式,包括内存对齐、大小端存储等概念,并详细探讨了张量数据在内存中的排布,如行优先与列优先排布,以及在深度学习中常见的NCHW与NHWC两种数据布局方式。这些布局方式的选择直接影响到程序的性能,尤其是在GPU和CPU上的表现。此外,还讨论了连续与非连续张量的概念及其对性能的影响。
65 3