思想
分而治之
- divide: 將數(shù)組從中間分成左右兩個(gè)子數(shù)組
- conquer：使用遞歸對(duì)子數(shù)組進(jìn)行排序
- combine： 合并有序子數(shù)組
代碼
include<stdio.h>
//對(duì)兩個(gè)有序子數(shù)組進(jìn)行融合
void merge(int Arr[],int L, int M,int R)
{
int LEFT_SIZE = M - L + 1;
int RIGHT_SIZE = R - M;
int left[LEFT_SIZE];
int right[RIGHT_SIZE];
int i ;
int j;
for (i = 0;i < LEFT_SIZE;i++)
left[i] = Arr[L+i];
for(j = 0; j < RIGHT_SIZE; j++)
right[j] = Arr[M+j+1];
/*for (i = 0; i < RIGHT_SIZE;i++)
printf("%d ",right[i]);
printf("\n");
*/
int k = L;
i = 0;
j = 0;
while(i < LEFT_SIZE && j < RIGHT_SIZE)
{
if(left[i] < right[j])
{
Arr[k] = left[i];
i++;
k++;
}
else
{
Arr[k] = right[j];
j++;
k++;
}
}
while(i<LEFT_SIZE)
{
Arr[k] = left[i];
i++;
k++;
}
while(j<RIGHT_SIZE)
{
Arr[k] = right[j];
j++;
k++;
}
}
//遞歸
void merge_sort(int Arr[],int L,int R)
{
if (L==R)
return;
else
{
int M = (L+R) / 2;
merge_sort(Arr,L,M);
merge_sort(Arr,M+1,R);
merge(Arr,L,M,R);
}
}
int main(void)
{
int a[] = {2,1,4,0,3,5,2,3,12};
int L = 0;
int R = sizeof(a) / sizeof(int) - 1;
merge_sort(a,L,R);
int i;
for (i=0;i <=R;i++)
printf("%d\n",a[i]);
printf("\n");
return 0;
}
