[数据结构]———归并排序

简介: [数据结构]———归并排序

1.基本思想:



归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide andConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 归并排序核心步骤:


image.png


2. 代码解析


1.分析

归并排序的逻辑过程可以通过几个关键步骤来可视化:


分解: 数组最初被分成两个子数组,这个过程递归进行,直到每个子数组只有一个元素。

合并: 递归结束后,开始合并过程,将相邻的两个有序子数组比较元素大小,较小的元素会被先放到临时数组中。

完整排序: 通过不断合并子数组,最终得到完全排序的数组


_MergeSort 函数 是递归函数,负责实际的排序工作。

输入参数:a 是待排序的数组指针,begin 和 end 分别表示当前子数组的起始和结束下标,tmp 是一个临时数组用于辅助合并两个已排序的子数组。

当 begin >= end 时,说明当前子数组只剩一个元素或为空,无需排序,直接返回。

计算中间点 mid,对左右两半 [begin, mid] 和 [mid+1, end] 分别递归调用 _MergeSort 进行排序。

调用结束后,通过比较并合并两个有序子数组 [begin, mid] 和 [mid+1, end] 到临时数组 tmp 中。

最后,将排好序的 tmp 数组复制回原数组 a 的相应位置。

MergeSort 函数 是主接口函数,负责初始化和释放临时数组。

动态分配与原数组相同大小的临时数组 tmp。
调用 _MergeSort 函数进行排序。
使用完毕后,释放临时数组 tmp 的内存。

2.逻辑图

6f8b67933e744c5793680a9f8cdf2230.gif


void _MergeSort(int* a, int begin, int end, int* tmp)
{
//划分
if (begin >= end)//只有一个元素不用划分
  return;
  int mid = (begin + end) / 2;//首尾下标相加除2得到中间点下标
  _MergeSort(a, begin, mid, tmp);//递归划分左半区域
  _MergeSort(a, mid + 1, end, tmp);//递归划分右半区域
  // [begin, mid][mid+1, end]归并
  int begin1 = begin, end1 = mid;//标记左半区第一个未排序的元素以及最后一个元素
  int begin2 = mid + 1, end2 = end;//标记右半区第一个未排序的元素以及最后一个元素
  int i = begin;//临时数组下标
  while (begin1 <= end1 && begin2 <= end2)
  {
  if (a[begin1] < a[begin2])//左半区第一个未排序的元素小于右半区第一个未排序的元素
  {
    tmp[i++] = a[begin1++];
  }
  else
  {
    tmp[i++] = a[begin2++];//右半区第一个未排序的元素小于左半区第一个未排序的元素
  }
  }
//合并左半区剩余元素
  while (begin1 <= end1)
  {
  tmp[i++] = a[begin1++];
  }
//合并右半区剩余元素
  while (begin2 <= end2)
  {
  tmp[i++] = a[begin2++];
  }
//把临时数组中合并后的元素拷贝回原数组
  memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
//归并排序入口
void MergeSort(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);//开辟一个辅助数组
  if (tmp == NULL)
  {
  perror("malloc fail");
  return;
  }
  _MergeSort(a, 0, n - 1, tmp);
  free(tmp);
}

3.运行结果

image.png

相关文章
|
4天前
|
算法
数据结构与算法-归并排序
数据结构与算法-归并排序
5 2
|
9天前
|
算法 C语言
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
9 0
|
10天前
|
搜索推荐
深入理解数据结构第六弹——排序(3)——归并排序
深入理解数据结构第六弹——排序(3)——归并排序
|
12天前
|
存储 算法 搜索推荐
【数据结构】归并排序的非递归写法和计数排序
【数据结构】归并排序的非递归写法和计数排序
|
1月前
|
搜索推荐 C语言
【数据结构】—超级详细的归并排序(含C语言实现)
【数据结构】—超级详细的归并排序(含C语言实现)
|
23天前
|
存储 搜索推荐 算法
[数据结构]————排序总结——插入排序(直接排序和希尔排序)—选择排序(选择排序和堆排序)-交换排序(冒泡排序和快速排序)—归并排序(归并排序)
[数据结构]————排序总结——插入排序(直接排序和希尔排序)—选择排序(选择排序和堆排序)-交换排序(冒泡排序和快速排序)—归并排序(归并排序)
|
1月前
|
搜索推荐 C语言
【C语言/数据结构】排序(归并排序|计数排序|排序算法复杂度)
【C语言/数据结构】排序(归并排序|计数排序|排序算法复杂度)
14 0
|
1月前
数据结构第六课 -------迭代排序(快速排序和归并排序)
数据结构第六课 -------迭代排序(快速排序和归并排序)
|
1月前
|
人工智能 算法 搜索推荐
数据结构——lesson12排序之归并排序
数据结构——lesson12排序之归并排序
|
1月前
|
人工智能 算法 搜索推荐
归并排序——“数据结构与算法”
归并排序——“数据结构与算法”