• 网站首页
• 网站建设
• 短视频
• 网站推广
• 网站模板
• 客户案例
• 资讯动态
• 关于我们

实现合并排序利用的算法是_java

当前位置：网站建设 > 技术支持

实现合并排序利用的算法是？

将集合等分排序

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

递归算法

void MergeSort(Type a[],int left,int right)//a为待排数组，left为左边界，right为右边界

{ if(left<right){//至少有两个元素，左右边界没有互换位置

int i = (left+right)/2;//取中点

MergeSort(a,left,i);

MergeSort(a,i+1,right);

Merge(a,b,left,i,right);//合并到数组b

Copy(a,b,left,right);//复制回数组a

}

}

非递归:首先将数组a中相邻元素两两配对。用合并算法将他们排序，构成n/2组长度为2的排好序的子数组段，然后再将他们排序成为长度为4的排好序的子数组段，如此继续下去，直至整个数组排好序

//消去递归后的合并排序算法

void MergeSort(Type a[],int n)

{

Type *b = new Type[n];

int s=1;

while(s<n){

MergePass(a,b,s,n);//合并到数组b

s+=s;

MergePass(b,a,s,n);//合并到数组a

s+=s;

}

}

//MergePass用于合并排好序的相邻数组段

void MergePass (Type x[],int s,int n)

{//合并大小为s的相邻子数组

int i=0;

while(i<=n-2*s){

//合并大小为s的相邻2段子数组

Merge(x,y,i+s-1,i+s*2-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(Type c[],Typed[],int l,int m,int r)

{

//合并c[l:m]和c[m+1:r]到d[l:r]

int i=l,i=m+1,k=1;

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];

}

版权说明：
本网站凡注明“广州京杭 原创”的皆为本站原创文章，如需转载请注明出处！
本网转载皆注明出处，遵循行业规范，如发现作品内容版权或其它问题的，请与我们联系处理！
欢迎扫描右侧微信二维码与我们联系。