歸并排序是利用歸并的思想對數(shù)列進(jìn)行排序瞄桨。--將兩個有序數(shù)列合并成一個有序數(shù)列话速，稱之為“歸并”，歸并包括從上往下和從下往上兩種方式芯侥。
- 從下往上的歸并排序 :將待排序數(shù)組分成若干個長度為1的子數(shù)列泊交，然后再將這些數(shù)列兩兩合并，得到若干個長度為2的有序數(shù)列柱查，再將這些數(shù)列兩兩合并；得到若干個長度為4的有序數(shù)列，再將它們兩兩合并直到合并為一個數(shù)列為止狞膘，這樣就得到最終結(jié)果乏盐。
-
從上往下的歸并排序 :它與從上往下的在排序方向上是相反的，包括三步：
(1): 分解----將當(dāng)前區(qū)間一分為二淋硝，即求分裂點(diǎn)mid=(low+high)/2;
(2): 求解----遞歸的對兩個子區(qū)間a[low...mid]和a[mid+1...high]進(jìn)行歸并排序雹熬，遞歸的終結(jié)條件是子區(qū)間的長度為1.
(3):合并----將已經(jīng)排好序的兩個子區(qū)間a[low...mid]和a[mid+1...high]歸并為一個有序的區(qū)間a[low...high].
歸并排序的時(shí)間復(fù)雜度和穩(wěn)定性
歸并排序的時(shí)間復(fù)雜度是O(NlgN):歸并排序的形式是一顆二叉樹，他需要遍歷的次數(shù)就是二叉樹的深度谣膳。而根據(jù)完全二叉樹可以得出他的時(shí)間復(fù)雜度是O(NlgN).
歸并排序的穩(wěn)定性
歸并排序是穩(wěn)定的算法
1.從上往下的歸并排序
void Merge(int *a,int start,int mid,int end,int *tmp)
{
int i=start;
int j=mid+1;
int k =0;
while(i<=mid && j<=end)
{
if(a[i]<=a[j])
tmp[k++] = a[i++];
else
tmp[k++] = a[j++];
}
while(i<=mid)
tmp[k++] = a[i++];
while(j<=end)
tmp[k++] = a[j++];
for (i = 0; i<k; ++i)
a[start+i] = tmp[i];
return ;
}
void Merge_Step(int *a,int start,int end,int *tmp)
{
if(start<end)
{
// int mid = (end+start)/2;
// int mid = start+(end-start)/2;
int mid = start+((end-start)>>1);
//這里和上面是一樣的但是可以解決end和start都很大的情況下竿报，start+end溢出的情況
Merge_Sort(a,start,mid,tmp);
Merge_Sort(a,mid+1,end,tmp);
Merge(a,start,mid,end,tmp);
}
}
void Merge_Sort(int *a,int len)
{
int i=0;
int n=len-1;
int *tmp = (int *)malloc(len*sizeof(int));
Merge_Step(a,0,n,tmp);
free(tmp);
}
２．從下往上的歸并排序
void Merge(int *a,int start,int mid,int end,int *tmp)
{
int i=start;
int j=mid+1;
int k =0;
while(i<=mid && j<=end)
{
if(a[i]<=a[j])
tmp[k++] = a[i++];
else
tmp[k++] = a[j++];
}
while(i<=mid)
tmp[k++] = a[i++];
while(j<=end)
tmp[k++] = a[j++];
for (i = 0; i<k; ++i)
a[start+i] = tmp[i];
return ;
}
void Merge_step(int *a,int len,int step,int *tmp)
{
int i =0;
for (; i+2*step-1 < len; i+=2*step)
Merge(a,i,i+step-1,i+2*step-1,tmp);
if (i+step-1 < len-1)
Merge(a,i,i+step-1,len-1,tmp);
}
int Merge_Sort(int *a,int len)
{
assert(a);
int *tmp = (int *)malloc(len*sizeof(int));
if(NULL == tmp)
return -1;
int i=1;
for (; i < len; i<<1)
Merge_step(a,len,i,tmp);
free(tmp);
}
