【算法】归并排序

云惠网小编 2021年11月25日09:18:31
评论
1957字阅读6分31秒
摘要

前几天卡一个警告卡了几天,vs2019真让人头秃直接进入正题吧。之前介绍的排序算法:【算法】插入排序——希尔排序+直接插入排序_Rinne’s blog-CSDN博客【算法】选择排序——堆排序+直接选择排序_Rinne’s blog-CSDN博客【算法】交换排序——快速排序+冒泡排序(更新了非递归冒泡以及优化)_Rinne’s blog-CSDN博客归并排序归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conque.

广告也精彩

但需要注意数组越界的问题,刚才的例子是以偶数数组为例

如果是奇数会存在数组越界的问题


归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有 序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

2. 代码


2. 代码

1. 图解思路

在这里插入图片描述


在这里插入图片描述



在这里插入图片描述

  • 情况1:begin2 和 end2 都越界

在这里插入图片描述


二、归并排序-非递归

在这里插入图片描述

时间复杂度: O(n*logn)

以此类推 i = i + gap后

在这里插入图片描述

归并排序

递归退出条件:

在这里插入图片描述

在这里插入图片描述

最后gap = 4的时候,再执行一次

1. 图解思路

之前介绍的排序算法:

开始作比较,放到tmp里面,再拷贝回原数组

  • 【算法】插入排序——希尔排序+直接插入排序_Rinne’s blog-CSDN博客
  • 【算法】选择排序——堆排序+直接选择排序_Rinne’s blog-CSDN博客
  • 【算法】交换排序——快速排序+冒泡排序(更新了非递归冒泡以及优化)_Rinne’s blog-CSDN博客


将刚才偶数例子去除一个数

空间复杂度:O(n)

在这里插入图片描述

将刚才偶数数组加上一个数

3. 测试

情况3:end1 越界

退出循环条件:gap >= n

vs2019可能会出现

在这里插入图片描述

其实就是不用归并

奇怪的警报,但是我测试了很多用例都没事


前几天卡一个警告卡了几天,vs2019真让人头秃
直接进入正题吧。


以此类推

//归并排序
void _MergeSort(int* a, int left, int right, int* tmp)
{
if (left >= right)
{
return;
}
int mid = (left + right) / 2;
//左右递归,
_MergeSort(a, left, mid, tmp);
_MergeSort(a, mid + 1, right, tmp);
int begin1 = left;
int end1 = mid;
int begin2 = mid + 1;
int end2 = right;
int i = left;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] > a[begin2])
{
tmp[i++] = a[begin2++];
}
else
{
tmp[i++] = a[begin1++];
}
}
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
//tmp数组拷贝回a
for (int j = left; j <= right; ++j)
{
a[j] = tmp[j];
}
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
printf("malloc fail");
exit(-1);
}
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
tmp = NULL;
}

一、归并排序-递归

在这里插入图片描述

在这里插入图片描述

  • 情况2:end2 越界
if (left >= right)
{
return;
}

文章目录

  • 归并排序
    • 一、归并排序-递归
      • 1. 图解思路
      • 2. 代码
      • 3. 测试
    • 二、归并排序-非递归
      • 1. 图解思路
      • 2. 代码
      • 3. 运行结果

可能是编译器错误

3. 运行结果

//归并非递归
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
printf("malloc fail");
exit(-1);
}
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i;
int end1 = i + gap - 1;
int begin2 = i + gap;
int end2 = i + 2 * gap - 1;
int index = i;
if (end1 >= n || begin2 >= n)
{
break;
}
if (end2 >= n)
{
end2 = n - 1;
}
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
//tmp数组拷贝回a
for (int j = i; j <= end2; ++j)
{
a[j] = tmp[j];
}
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}

本文转自 https://blog.csdn.net/qq_53656490/article/details/121510513

腾讯云618
云惠网小编
cgb2110-day06 java

cgb2110-day06

文章目录一,模拟用户登录过程--1,需求--2,测试--3,程序优化二,SQL攻击/注入--1,概述--2,解决方案--3,修改代码--4,两种传输器的区别三,练习新的传输器--1...
JAVA 初级程序员常见问题分析 java

JAVA 初级程序员常见问题分析

1、怎么样可以尽快拿到offer?针对心仪的企业、岗位进行调查。可以上招聘网站看看其岗位要求,以及企业的面试题。然后针对性的学习其要求的技术。这样有针对性的准备,投其所好,就可更快...
关于数据库学习的一些知识盲区 java

关于数据库学习的一些知识盲区

一.SQL拼接方法的安全风险 1. SQL注入问题(SQL Inject),使用字符串拼接构造SQL就会引起SQL注入。 2. SQL注入是存在安全风险的 3. 例如:在图书管理系...
szu-exp 安卓开发实验3我的校园 java

szu-exp 安卓开发实验3我的校园

发扬开源精神... 给个赞吧giegiejiejie们 实验目的与要求: 目的:掌握安卓中活动的编写、自定义用户界面的开发、碎片开发、广播机制以及数据持久化技术等;并能通过对课堂知...
腾讯云618

发表评论