排序算法分享：归并排序！

2020-10-24 09:00

TXP嵌入式

关注

c、如下图所示，两个指针都指向了数字5，如果遇到两个数字一样的话，一般是把第一个序列的数字放到临时数组res里面去，这点稍微要注意一下

d、最后把临时数组里面的是数字放到原来的数组里面去

注意：一个算法稳定，并不能说它的时间效率是稳定的；这里的稳定是说两个序列中有两个数是相同的，如果在排完序之后，他们的位置还是没有发生变化的话，那么这个排序就是稳定的，反之亦然！

3、归并排序的平均时间复杂度的计算推导：

从图片的纵性来分析，当拆解到1的时候，这个时候什么数等于n除于它等于1，通过计算，我们知道是logn，然后再从横向分析，我们要最多比较n个数字，所以归并排序的时间复杂度就是：nlogn

二、代码示例：

代码：

＃include ＜iostream＞
using namespace std；
const int N ＝ 1e5 ＋ 10；
int n；
int q［N］， tmp［N］；
void merge＿sort（int q［］，int l， int r）
｛
if（l＞＝r）return；／／判断序列中是否为空或者只有一个数字，如果是的话，我们就不用排序了
／／确定分界点
int mid ＝ l ＋ r ＞＞ 1；
／／递归处理
merge＿sort（q，l，mid）；
merge＿sort（q，mid＋1，r）；
／／定义双指针
int k ＝0，i ＝ l， j＝ mid＋1；
／／归并处理
while（i ＜＝ mid ＆＆ j ＜＝ r）
if（q［i］＜ q［j］）tmp［k＋＋］＝ q［i＋＋］；
else
tmp［k＋＋］＝ q［j＋＋］；
／／把源数组中剩余的数字（注意这里的数字一定是最小的）放到临时数组后面去
while（i ＜＝ mid）tmp［k＋＋］＝ q［i＋＋］；
while（j ＜＝ r）tmp［k＋＋］＝ q［j＋＋］；
／／把临时数组中排好序的数字放到源数组中去
for（i ＝ l， j ＝0；i＜＝r；i＋＋，j＋＋）q［i］＝tmp［j］；
｝
int main（）
｛
scanf（＂％d＂，＆n）；
for（int i ＝ 0；i＜n；i＋＋）
｛
scanf（＂％d＂，＆q［i］）；
｝
merge＿sort（q，0，n－1）；
for（int i ＝ 0； i＜n；i＋＋）
｛
printf（＂％d ＂，q［i］）；
｝
return 0；

｝