数据结构与算法学习笔记之 适合大规模的数据排序

前言

在数据排序的算法中，不同数据规模应当使用合适的排序算法才能达到最好的效果，如小规模的数据排序，可以使用冒泡排序、插入排序，选择排序，他们的时间复杂度都为O（n²），大规模的数据排序就可以使用归并排序和快速排序，时间复杂度为O（nlogn）。今天我们就来看一下归并排序和快速排序。

正文

归并排序的原理

核心思想（分治思想）：

排序数组，将数组从中间分成前后两部分，对前后两部分分别排序，然后合在一起，这个数组就是有序的。

归并排序的性能分析

1.归并排序是一个稳定的排序算法：在合并的过程中，如果A[p...q]和A[q+1...r]之间中有相同的元素，先把A[p...q]中的元素放入tmp数组。这样就保证了值相同的元素，在合并前后的先后顺序不变。

2.归并排序的时间复杂度是O（nlogn）：在解决递归问题时，我们得出一个结论：递归问题可以写成递推公式，递归代码的时间复杂度也可以写成递推公式

我们假设对n个元素进行归并排序需要的时间是T（n），那分解成两个子数组排序的时间都是T(n/2)，套用结论可以得到归并排序的时间复杂度的计算公式就是：

<pre style="margin: 0px 0px 15px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Monaco, Menlo, Consolas, "Courier New", monospace; font-size: 12px !important; line-height: 1.72222; color: inherit; border-radius: 2px; background: rgb(238, 238, 238); border: 0px; overflow: auto;">T(1) = C； n=1 时，只需要常量级的执行时间，所以表示为 C。
T(n) = 2*T(n/2) + n； n>1</pre>

再次将这个公式分解:

<pre style="margin: 0px 0px 15px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Monaco, Menlo, Consolas, "Courier New", monospace; font-size: 12px !important; line-height: 1.72222; color: inherit; border-radius: 2px; background: rgb(238, 238, 238); border: 0px; overflow: auto;">T(n) = 2T(n/2) + n = 2(2T(n/4) + n/2) + n = 4T(n/4) + 2n = 4(2T(n/8) + n/4) + 2n = 8T(n/8) + 3n = 8(2T(n/16) + n/8) + 3n = 16T(n/16) + 4*n
...... = 2^k * T(n/2^k) + k * n
......</pre>

我们可以得到T(n)=2^kT(n/2k)+kn.当T(n/2^{k)=T(1)时，也就是n/2}k=1,我们将得到k=log₂n，问你将k带入公式得到

T(n)=Cn+nlog2n

用大O标记法来表示为T(n) 就等于 O(nlogn)

而且时间复杂度是非常稳定的：最好情况，最坏情况，还是平均情况，时间复杂度都是O（nlogn）

3、归并排序的空间复杂度为O（n）

归并排序的致命缺点：归并排序不是原地排序算法（在合并两个有序数组时，需要借助额外的存储空间）

递归代码的空间复杂度并不能像时间复杂度那样累加、尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后、临时开辟的内存空间就被释放掉了、临时内存空间最大也不会超过 n 个数据的大小

快速排序的原理

如果要排序数组中下标从p到r之间的一组数据，我们选择p到r之间的任意一个数据作为pivot（分区点），遍历数据，见小于pivot的放在右边，大于pivot放在左边。这样数组就分成了三部分，用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1.到r之间的数据，直到区间缩小为1，说明数据都有序
　　快速排序的时间复杂度为O（1）：在排序过程中，假如遇到需要移动数据的，我们可以之间用交换的思想

image

（图片来源于网络，侵删）

空间复杂度为O（1）

快速排序和归并排序的区别？

看图：

image

（图片来源于网络，侵删）

处理过程的差异：

递归排序：先处理子问题再合并

快速排序：先分区，再处理子问题

归并排序虽然稳定，是时间复杂度为O（nlogn）的排序算法，但是它不是原地排序算法，合并过程中需要额外的空间。

快速排序的性能分析

递归代码的时间复杂度，如果每次分区操作，都能正好将数组分为两个大小相等的两个小区间，那快速排序的递推公式和递推排序是相同的，所以，快排的时间复杂度为O（nlogn）

但是，每次都分得那么均匀是非常难实现的。

T（n）在大部分情况下的时间复杂度都可以做到O（nlogn），只有在极端情况下才会退化为O（n²）.

后记

递归和快排都是分治的思想，代码都通过递归来实现，过程非常相似。归并排序时间复杂度都非常稳定为O（nlogn），但是每次合并的时候都需要额外的空间，空间复杂度非常高为是O(n)，快速排序算法虽然最坏时间复杂度为O（n²），但是平均时间复杂度为O（nlogn），最坏的情况我们也可以避免。

相关文章

数据结构与算法学习笔记之写链表代码的正确姿势（下）

数据结构与算法学习笔记之 提高读取性能的链表（上）

数据结构与算法学习笔记之 从0编号的数组

数据结构与算法学习笔记之后进先出的“桶”

数据结构与算法学习笔记之先进先出的队列

数据结构与算法学习笔记之高效、简洁的编码技巧“递归”

数据结构与算法学习笔记之如何分析一个排序算法？

以上内容为个人的学习笔记，仅作为学习交流之用。

![LT8[X9E7]RLI}L]UROFK(`D.png](https://upload-images.jianshu.io/upload_images/14464859-7c72a73cc3dbc875.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

欢迎大家关注公众号，不定时干货，只做有价值的输出

作者：Dawnzhang
出处：https://www.cnblogs.com/clwydjgs/

小舟从此逝，江海寄余生。 --狐狸