791
經典白話算法之歸並排序
void Merge(int A[],int p,int q,int r){
int i,j,k;
//計算子數組A[p..q]的元素個數
int n1 = q - p + 1;
//計算子數組A[q+1..r]元素個數
int n2 = r - q;
//創建子數組L，R
int* L = (int*)malloc(sizeof(int)*(n1+1));
int* R = (int*)malloc(sizeof(int)*(n2+1));
//將子數組A[p..q]賦值到L數組
for(i = 0;i < n1;i++){
L[i] = A[p+i];
}//for
//將子數組A[q+1..r]賦值到R數組
for(i = 0;i < n2;i++){
R[i] = A[q+1+i];
}//for
//將哨兵置於數組末尾
L[n1] = INT_MAX;
R[n2] = INT_MAX;
//合並
i = 0;j = 0;
for(k = p;k <= r;k++){
if(L[i] <= R[j]){
A[k] = L[i++];
}else{
A[k] = R[j++];
}
}//for
}
void MergeSort(int A[],int p,int r){
//容錯
if(p >= r){
return;
}
//分治
int mid = (r + p) / 2;
//遞歸調用
MergeSort(A,p,mid);
MergeSort(A,mid+1,r);
//Cmbine
Merge(A,p,mid,r);
}
調用：
int a[] = {1,3,5,7,8,2,3,5,6,9};
MergeSort(a,0,9);
最後更新：2017-04-03 12:56:32