個人對歸并排序的理解
1.也是分治法
2.先拆分，拆分總序列娶牌， （先不考慮奇數(shù)）
第一次拆分為N個子序列, 每個子序列元素有1個寒瓦，倆倆合并子序列
第二次拆分為N/2子序列于颖，每個子序列元素有2個迟几， 倆倆合并子序列
第三次拆分為N/4子序列消请，每個子序列元素有4個，倆倆合并子序列
----------n/2^n ------------------ 2^n
...最后拆分為2個子序列类腮，每個子序列元素有N/2個臊泰，倆倆合并子序列，成為新的有序序列
3.因?yàn)椴鸱值淖有蛄卸际怯行虻难潦啵喜⑺俣确浅因宇？炱哂ぁw并效率很高
時間復(fù)雜度
平均速度 O(N*logN)
穩(wěn)定排序
#include <iostream>
using namespace std;
void print(int a[], int n){
for(int j= 0; j<n; j++){
cout<<a[j] <<" ";
}
cout<<endl;
}
//將r[i…m]和r[m +1 …n]歸并到輔助數(shù)組rf[i…n]
void Merge(int *r,int *rf, int i, int m, int n)
{
int j,k;
for(k=i,j=m+1; i<=m && j <=n ; ++k){
if(r[j] < r[i]) rf[k] = r[j++];
else rf[k] = r[i++];
}
while(i <= m) rf[k++] = r[i++];
while(j <= n) rf[k++] = r[j++];
// print(rf,n+1);
}
void MergeSort(int *r, int *rf, int lenght)
{
int len = 1;
int *q = r ;
int *tmp ;
while(len < lenght) {
len = 2 * len ;
int i = 0;
while(i+ len <lenght) {
Merge(q, rf, i, i+ len/2 -1, i+ len-1 ); //對等長的兩個子表合并
i = i+ len;
}
if(i + len/2 < lenght+1){ // 這里要+1
Merge(q, rf, i, i+ len/2 -1, lenght -1); //對不等長的兩個子表合并
}
tmp = q; q = rf; rf = tmp; //交換q,rf，以保證下一趟歸并時察滑，仍從q 歸并到rf
}
}
int main(){
int a[19] = {3,1,5,7,2,4,9,6,8,0,20,3,5,6,7,-1,-1,-2,0};
int b[19];
MergeSort(a, b,19);
cout<<"結(jié)果：";
print(b,19);
}
-
看我那么可愛n(≧▽≦)n
- 關(guān)注我的微薄 (梁同桌)：http://weibo.com/tongrenyinsheng
- 個人博客： http://www.liangtongzhuo.com
- ios 個人寫的app （同人音聲）ASMR音樂
