Day22【概念解析】归并排序

type

status

date

slug

summary

整理定义

出处	定义
中国大百科全书	建立在归并操作上的一种有效的排序算法，此算法采用分治法实现序列的排序。又称归并排序。
百度百科	归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
维基百科	In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the relative order of equal elements is the same in the input and output. Merge sort is a divide-and-conquer algorithm that was invented by John von Neumann in 1945.[2] A detailed description and analysis of bottom-up merge sort appeared in a report by Goldstine and von Neumann as early as 1948. 【在计算机科学中，合并排序（通常也拼写为 mergesort）是一种高效、通用且基于比较的排序算法。大多数实现都会产生稳定的排序，这意味着相等元素的相对顺序在输入和输出中是相同的。归并排序是一种分治算法，由约翰·冯·诺依曼于 1945 年发明。[2] 早在 1948 年 Goldstine 和 von Neumann 的报告中就出现了对自下而上归并排序的详细描述和分析。】

复述展开

归并排序，又称为合并排序，采用分治法进行序列排序，是一种稳定性的排序算法，算法复杂度为O(nlogn)。

代码演示：

动图演示：

理解体会

归并排序是一种分治算法，其基本思想是将两个或两个以上的有序表合并成一个新的有序表。具体步骤如下：

分解：将当前区间一分为二，递归地对它们进行分解，直到分解到一个元素为止。

合并：将分解出的数列合并，合并过程为：将两个有序数列合并成一个有序数列，我们称之为二路归并。

特点：

稳定性：归并排序是一种稳定的排序方法，即相等的元素的顺序不会改变。

非原地排序：归并排序需要额外的空间来存储元素，因此空间复杂度为O(n)。

优点：

对于大规模数据的排序，归并排序是非常有效的。因为其时间复杂度为O(nlogn)，这在所有的时间复杂度为O(nlogn)的排序算法中，性能表现最稳定。

归并排序适合对链表进行排序，因为链表的节点分布可以看作是随机的，归并排序只需要重新排列链表节点的指针即可。

缺点：

需要额外的存储空间，空间复杂度为O(n)。

对于小规模数据，插入排序等简单排序算法可能更有效。

使用场景：

处理大规模数据：归并排序适合处理大规模数据，因为其时间复杂度为O(nlogn)。

链表排序：归并排序是链表排序的最佳选择，因为它不需要随机访问元素。

对比同类算法：

快速排序：快速排序在最坏情况下的时间复杂度为O(n^2)，而归并排序在所有情况下的时间复杂度都是O(nlogn)。但是，快速排序是原地排序，不需要额外的存储空间，而归并排序需要。

堆排序：堆排序和归并排序的时间复杂度都是O(nlogn)，但堆排序是原地排序算法，而归并排序不是。然而，堆排序不是稳定的排序算法，而归并排序是。

总结：归并排序是一种高效、稳定、但非原地的排序算法。它对处理大规模数据和链表排序非常有效。但是，由于其需要额外的存储空间，对于存储空间有限或者数据规模较小的情况，可能不如其他排序算法有效。

📌

快速跳转链接

【概念解析】启动

【活动打卡】写100个行业概念 | 易浅小站

为什么要参加这个活动呢？起源于S老师的”写100个行业概念“活动。之前一直有关注Scalers老师的公众号，也阅读完了《学习的学问》这本书，感叹于S老师学习成长会的魅力，决定先让自己跟着这个活动坚持个一百天先。

整理定义

复述展开

理解体会

eachenkuang