数据结构与算法-----归并排序
浏览数:36 

归并排序(递归合并)

平均时间复杂度O(2NlogN),稳定,对数据有序性不敏感,非就地排序,不适用于对海量数据进行排序。

#include<iostream>

#include<cstdlib>

#include<cstring>

using namespace std;

/*异地合并(将合并的结果放在新的数组中)*/

void remoteMerge(int *arr1,int size1,int *arr2,int size2,int *arr3){

int i=0,j=0,k=0;

for(;;){

if(i<size1 && j<size2){

if(arr1[i]<=arr2[j]){

arr3[k++]=arr1[i++];

}

else

arr3[k++]=arr2[j++];

}

else if(i<size1)

arr3[k++]=arr1[i++];

else if(j<size2)

arr3[k++]=arr2[j++];

else

break;

}

}

/*本地合并(将合并的结果放在当前数组中,-->调用异地合并方法)*/

void localMerge(int *arr,int left,int middle,int right){

int size=right-left+1;

int res[size];

remoteMerge(arr+left,middle-left+1,arr+middle+1,right-middle,res);

for(int i=0;i<size;++i)

arr[left+i]=res[i];

}

/*归并排序(使用递归的思想调用本地合并方法的一种排序方法)*/

void mergeSort(int *data,int left,int right){

if(left<right){

int middle=(left+right)/2;

mergeSort(data,left,middle);

mergeSort(data,middle+1,right);

localMerge(data,left,middle,right);

}

}

int main(){

/*测试异地合并

int arr1[11]={-12,1,3,5,7,9,10,12,13,14,20};

int arr2[11]={-2,0,2,4,6,8,10,12,14,16,17};

int arr3[22]={0};

remoteMerge(arr1,11,arr2,11,arr3);

for(int i=0;i<22;++i){

cout<<arr3[i]<<' ';

}

cout << endl;

*/

/*测试本地合并

int arr4[10]={25,26,28,100,2,3,4,5,23,120};

localMerge(arr4,0,3,9);

for(int i=0;i<10;++i){

cout<<arr4[i]<<' ';

}

cout << endl;

*/

/*测试归并排序*/

int *data=new int;

int size;

cout<<"Pls input the size:";

cin>>size;

srand(time(0));

for(int i=0;i<size;++i){

//*(data+i)=rand()%100;

data[i]=rand()%100;

}

mergeSort(data,0,size-1);

for(int i=0;i<size;++i){

cout<<data[i]<<' ';

}

cout << endl;

return 0;

}


联系管理员
 
 
 
 
 工作时间
周一至周五 :9:30-17:30
马上建站
会员登录
登录
我的资料
留言
回到顶部