当前位置: 首页> 教育> 大学 > 数据结构C++——分而治之算法

数据结构C++——分而治之算法

时间:2025/7/10 8:49:57来源:https://blog.csdn.net/qq_60987997/article/details/140673096 浏览次数:0次

一、思想

divide - conquer

  • 把问题分解成两个或多个更小的问题
  • 分别解决每个小问题
  • 把各小问题的解答组合起来,即可得到原问题的解

二、 归并排序

Merge Sort

  • 利用分而治之方法进行排序算法
  • 将n 个元素按非递增顺序排列
    • 若n 为1,算法终止(base)
    • 否则
      将这一元素集合分割成两个或更多个子集合
      对每一个子集合分别排序
      将排好序的子集合并为一个集合
template<class T>
mergeSort( T *a, int left, int right)
{//对a[left:right]中的元素进行排序if (left < right) {//至少两个元素int middle = (left + right)/2; //中心位置mergeSort(a, left, middle);mergeSort(a, middle +1, right);merge(a, b, left, middle, right); //从a合并到bcopy(b, a, left, right); //排序结果复制到a}
}

在这里插入图片描述

分段:

template<class T>
void mergeSort(T a[], int n)
{// 使用归并排序算法对a[0:n-1] 进行排序T *b = new T [n];int segmentSize = 1; // 段的大小while (segmentSize < n) {mergePass(a, b, segmentSize, n); // 从a归并到bsegmentSize += segmentSize;mergePass(b, a, segmentSize, n); // 从b 归并到asegmentSize += segmentSize;}
}template<class T>
void merge(T c[]
关键字:数据结构C++——分而治之算法

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: