c语言中的merge函数

Python017

c语言中的merge函数,第1张

merge()是C++标准库的函数，主要实现函数的排序和合并，不仅仅是合并，具体要求参照标准库。

#include"stdafx.h"

#include<iostream>

#include<algorithm>

#include<array>

#include<list>

usingnamespacestd

boolcomp(constinti,constintj){

returni>j

}

intmain(void){

/*自定义谓词*/

std::array<int,4>ai1={1,3,4,5}

std::list<int>lsti1

for(constauto&i:ai1)

lsti1.push_front(i)//从大到小

std::array<int,4>ai2={2,6,7,8}

std::list<int>lsti2

for(constauto&i:ai2)

lsti2.push_front(i)

lsti1.merge(lsti2,comp)

std::cout<<"merge(>):"

for(constauto&i:lsti1)

std::cout<<i<<""

std::cout<<std::endl

/*默认谓词*/

std::array<int,4>ai1d={1,3,4,5}

std::list<int>lsti1d

for(constauto&i:ai1d)

lsti1d.push_back(i)//从小到大

std::array<int,4>ai2d={2,6,7,8}

std::list<int>lsti2d

for(constauto&i:ai2d)

lsti2d.push_back(i)

lsti1d.merge(lsti2d)

std::cout<<"merge(<):"

for(constauto&i:lsti1d)

std::cout<<i<<""

std::cout<<std::endl

return0

}

扩展资料

Merge算法的两种接口，把两个有序的数组合并到另一个数组中：

void Merge(int *A, int f, int m, int e){

int temp[e-f+1]

int i,first=f,last=m+1

for(i=0i<(e-first+1)&&f<=m&&last<=ei++){

if(A[f]<=A[last]) {

temp[i]=A[f]

f++

}

else {

temp[i]=A[last]

last++

}

}

while(f>m&&last<=e){

temp[i]=A[last]

i++

last++

}

while(f<=m&&last>e){

temp[i]=A[f]

i++

f++

}

for(i=0first<=ei++,first++){

A[first]=temp[i]

}

}

参考资料来源：百度百科—c语言

void MergeSort(int x[],int n) { //非递归归并排序

//元素数组为x，其长度为n

int i,j,k1,k2,l

int *a

for(i=1i<=n-1i=i*2)//i为插入排序的子段长度

{

for(j=1j<=n-1j=j+2*i)//j为进行插入排序的子段起始位置

{

a=(int *)malloc(2*i*sizeof(int))

l=0k1=jk2=j+i

while((l<2*i)&&(k2<=n-1)&&(k2<j+2*i)&&(k1<j+i))

{//子段中，比较，移至辅助内存

if(x[k1]<x[k2])

{

a[l++]=x[k1]k1++

}

else

{

a[l++]=x[k2]k2++

}

}

if((k2>n-1)||(k2>=j+2*i))

{//子段的后一段超出数组范围

for(k1<j+ik1++)

a[l++]=x[k1]

}

else//就只有第一段就超数组了

{

if(k1>=j+i)

{

for((k2<j+2*i)&&(k2<=n-1)k2++)

a[l++]=x[k2]

}

}

for(k1=0k1<lk1++)//最后移位

{

x[j+k1]=a[k1]

}free(a)

}

}

}

非递归的归并排序，我以前写的。

中间malloc与free的话，是为了方便管理不定大小的空间，这里需要malloc.h的头文件