`
blogfeifei
  • 浏览: 1187908 次
文章分类
社区版块
存档分类
最新评论

算法中分治策略实现合并排序

 
阅读更多

合并排序算法是用分治策略实现对n个元素进行排序的算法。其基本思想是:将待排序的元素分成大小大致相同的两个子集合,分别对两个子集合进行排序,最终排好序的子集合并成所要求的排好序的集合。

#include<iostream>
using namespace std;
void mergePass(int x[],int y[],int s,int n);
void merge(int c[],int d[],int l,int m,int r);
void mergeSort(int a[],int n)
{
int *b = new int[n];
int s = 1;
while(s<n)
{
mergePass(a,b,s,n);//合并到数组b
s+=s;
mergePass(b,a,s,n);//合并到数组a
s+=s;
}
for(int an=0;an<5;an++)
cout<<a[an]<<" ";
for(an=0;an<5;an++)
cout<<b[an]<<" ";
}
void mergePass(int x[],int y[],int s,int n)
{//合并大小为s的相邻子数组
int i = 0;
while(i<=n-2*s)
{//合并大小为s的相邻2段子数组
merge(x,y,i,i+s-1,i+2*s-1);
i = i+2*s;
}
//剩下的元素个数少于2s
if(i+s<n)
merge(x,y,i,i+s-1,n-1);
else for(int j = i;j<= n-1;j++) y[j] = x[j];
}
void merge(int c[],int d[],int l,int m,int r)
{//合并数组
int i = l,j = m+1,k = l;
while(i<=m&&j<=r)
if(c[i]<=c[j]) d[k++] = c[i++];
else d[k++] = c[j++];
if(i>m) for(int q = j;q<=r;q++) d[k++] = c[q];
else for(int q = i;q<=m;q++) d[k++] = c[q];
}


int main()
{
int arr[5]={100,25,3,1,7};
mergeSort(arr,5);
return 0;
}

分享到:
评论

相关推荐

    合并排序(分治策略)报告.doc

    算法设计与分析实验报告,附已通过源码,供学习参考,共勉♪ 目录摘要如下: 1.问题描述 2.实验目的 3.实验原理 4.实验设计 (包括输入格式、算法、输出格式) 5.实验结果与分析 (除了截图外,实验结果还用...

    合并排序算法的代码实现

    该合并排序算法是java实现用分治策略实现对n个元素进行排序的算法!其基本思想是:将待排序元素分成大小大致相同的2个子集合,分别对2个子集合进行排序,最终将排好序的子集合合并成为所要求的排好序的集合。

    第2章 分治策略2合并排序(MIT课件)

    问题提出: 已知n个元素的数组A[1:n],将A中元素按不降顺序排列。

    实验二:归并排序的分治策略设计

    实验步骤:利用分治策略编程实现合并排序,教材P21-22; 问题描述:合并排序(MERGE SORT),是用分之策略实现对n个元素进行排序的算法。合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列...

    分治法-归并排序

    分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解...

    《算法设计与分析》实验报告:实验一(分治策略)

    必做:n 用分治思想设计实现二分搜索、合并排序,并且用不同数据量进行实验对比分析。 选做:阶乘(递归与分治)。

    算法分析与设计之分治策略

    在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解...

    算法设计与分析.rar

    分治策略 内容: 用分治法实现一组无序序列的两路合并排序和快速排序。 要求:理解分治法的算法思想,清楚两路合并排序和快速排序算法的基本原理和实施过程,能将输入的一组无序序列排列为有序序列后输出。比较不同...

    合并排序(非递归算法)C语言

    合并排序非递归算法是学习计算机算法与实现的一种应用,可以巩固c语言所学的知识

    合并排序递归算法

    合并排序的递归调用和合并排序的非递归调用的对比,可以让人感受到选择递归调用可以提高工作作业效率,只要得到递归公式和递归出口就可以了,问题解决起来会很省力

    合并排序递归和非递归算法

    合并排序递归和非递归算法的实现可以让人理解到递归算法的实现有时候比非递归算法效率高很多,人只需要给出一个递归公式和一个递归出口,所有的事都可以交给计算机来完成了

    递归与分治策略.ppt

    理解递归的概念 掌握设计有效算法的分治策略:分治法的基本思想 通过范例学习分治策略的算法分析及设计技巧 二分搜索技术、大整数的乘法、Strassen矩阵乘法 合并排序和快速排序

    C语言用分治法实现数组归并排序算法实现

    2.加深对分治法算法设计方法的理解与应用; 3.锻炼学生对程序跟踪调试能力; 4.通过本次实验的练习培养学生应用所学知识解决实际问题的能力。 问题: 输入N个数对其进行归并排序。 解决策略: 分治法策略:...

    合并排序的c++源程序

    一个简单的合并排序的算法的演示过程。还不错。。

    递归与分治策略

    合并排序 循环赛日程表 递归算法:直接或者间接调用自身的算法称为递归算法。 适合递归算法的问题: 递归函数:用函数自身给出定义的函数。 递归结构:二叉树 可以转化为递归算法解决 例:递归函数—阶乘函数 n!=n*...

    根号n段归并排序算法

    根号n段归并排序算法的C++代码实现: 1.合并【根号n向下取整】段子数组,使用了自底向上的两两合并策略。 2.算法的总体时间复杂度为nlogn 3.带有详细注释

    递归与分治策略(从概念原理到多个实例的详细讲解)

    阶乘函数,Fibonacci数列,基于递归的插入排序,时间递归方程和复杂性分析,整数划分问题,Hanoi塔问题,分治法的适用条件,二分搜索算法,大整数的乘法,Strassen矩阵乘法, 棋盘覆盖,合并排序,快速排序

    快速排序算法

    其实快速排序的核心思想是分治策略,即先分解再递归求解,最后再合并。具体来说就是在待排序记录序列中选取一个记录(通常先选取第一个记录)为驱轴,其关键字设为K1,然后将其余关键字小于K1的记录移到前面,而将...

Global site tag (gtag.js) - Google Analytics