-
合併排序
鎖定
合併排序法是將兩個（或兩個以上）有序表合併成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然後再把有序子序列合併為整體有序序列。
將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱為2-路歸併。合併排序也叫歸併排序。
合併排序基本概念
複雜度
最壞時間複雜度
最好時間複雜度
空間複雜度
與快速排序類似
合併排序實現
合併排序JAVA
public static void mergeSort(int[]array){
int length=array.length;
int middle=length/2;
if(length>1){
int[]left=Arrays.copyOfRange(array,0,middle);//拷貝數組array的左半部分
int[]right=Arrays.copyOfRange(array,middle,length);//拷貝數組array的右半部分
mergeSort(left);//遞歸array的左半部分
mergeSort(right);//遞歸array的右半部分
merge(array,left,right);//數組左半部分、右半部分合併到Array
}
}
//合併數組，升序
private static void merge(int[]result,int[]left,int[]right){
int i=0,l=0,r=0;
while(l<left.length&&r<right.length){
if(left[l]<right[r]){
result[i]=left[l];
i++;
l++;
}else{
result[i]=right[r];
i++;
r++;
}
}
while(r<right.length){//如果右邊剩下合併右邊的
result[i]=right[r];
r++;
i++;
}
while(l<left.length){
result[i]=left[l];
l++;
i++;
}
}
合併排序C、C++語言
程序1
/****************************/
/*author:不辭遠*/
/****************************/
#include <malloc.h>
#include <stdlib.h>
void mergesort(int*a,int length){
int step;
int*p,*q,*t;
int i,j,k,len1,len2;
int *temp;
step=1;
p=a;
q=(int*)malloc(sizeof(int)*length);
temp=q;
while(step<length){
i=0;
j=i+step;
k=i;
len1=i+step<length?i+step:length;
len2=j+step<length?j+step:length;
while(i<length){
while(i<len1&&j<len2){
q[k++]=p[i]<p[j]?p[i++]:p[j++];
}
while(i<len1){
q[k++]=p[i++];
}
while(j<len2){
q[k++]=p[j++];
}
i=j;
j=i+step;
k=i;
len1=i+step<length?i+step:length;
len2=j+step<length?j+step:length;
}
step*=2;
t=p;
p=q;
q=t;
}
if(a!=p){
memcpy(a,p,sizeof(int)*length);
}
free(temp);
}
void main(void){
int arrary[]={9,6,1,3,8,4,2,0,5,7};
mergesort(arrary,10);
}
程序2
排序位於[begin, end]中的整數
void sort(int *begin,int *end)
{
int size=end-begin;
int*p,*p1,*p2,*mid=begin+size/2;
if(size<=1)return;//邊界條件
sort(begin,mid);//遞歸求解
sort(mid,end);
p=(int*)malloc(size*sizeof(int));//申請臨時空間
for(p1=begin,p2=mid;p1!=mid||p2!=end;)//合併有序表
*p++=(p2==end||p1!=mid&&*p1<*p2)?(*p1++):(*p2++);
for(p-=size;begin!=end;)//回填
*begin++=*p++;
free(p-size);//釋放臨時空間
}
程序3
//C++
#include<string>
#include<iostream>
using namespace std;//合併排序
//合併兩部分有序數組time:O(n)
template<typename T>
void Merge(T *arry,int start,int p,int end)
{
int lsize=p-start,rsize=end-p;//兩個數組的大小
T * l=new T[lsize],*r=new T[rsize];//要合併的兩個數組
memcpy(l,arry + start,sizeof(T)*lsize);
memcpy(r,arry + p,sizeof(T)*rsize);//將要合併的數組複製
int lnow=0,rnow=0,i;//未合併的數字的位置
for(i=0;lnow<lsize&&rnow<rsize;i++)
{
if(l[lnow]>r[rnow])//取較大的數
{
arry[start+i]=l[lnow];
lnow++;
}
else
{
arry[start+i]=r[rnow];
rnow++;
}
}
if(lnow==lsize&&rnow!=rsize)//其中一個數組合並完以後，複製剩下的數據
{
memcpy(arry+start+i,r+rnow,sizeof(T)*(rsize-rnow));
}
else if(rnow==rsize&&lnow!=lsize)
{
memcpy(arry+start+i,l+lnow,sizeof(T)*(lsize-lnow));
}
delete l;
delete r;//清理內存
//return ;
}//排序函數time:O(nlgn)
template<typename T>
void MergeSort(T *arry,int start,int end)
{
if(end-start > 1)//當元素個數為1時直接返回
{
int p=(start + end)/2;//切割數組
MergeSort(arry,start,p);
MergeSort(arry,p,end);//分別排序
Merge(arry,start,p,end);//合併數組
}
}
int main()
{
int arr[10]={7,3,4,7,10,9,1,5,3,7};
MergeSort(arr,0,10);
for(int i=0;i<10;i++)
{
cout<<arr[i]<<" "<<endl;
}
return 0;
}
