1. 简述
归并排序的原理是将,两个较大的数组分为大小几乎一致的两个数组。
再将两个数组进行合并成新的有序数组。
合并两个数组的时候需要额外的一个数组的空间。
2. 实现
上图说明过程
- 代码
#include <stdio.h>
void Merge(int *arr, int *tmp, int l, int center, int r) {
int lp = l;
int rp = center + 1;
int ptr = l;
while ( lp < center + 1 || rp < r + 1) {
if ( lp > center || (rp < r + 1 && arr[lp] > arr[rp]) )
tmp[ptr++] = arr[rp++];
else
tmp[ptr++] = arr[lp++];
}
for ( int i = l; i < r + 1; ++i)
arr[i] = tmp[i];
}
void mergeSort(int *arr,int *tmp, int l,int r) {
if ( l >= r)
return ;
int center = l + (r - l >> 1);
mergeSort(arr, tmp, l, center);
mergeSort(arr, tmp, center + 1, r);
Merge(arr, tmp, l, center, r);
}
int main() {
int arr[] = {5,1,3,7,8,4,2,6};
int tmp[] = {0,0,0,0,0,0,0,0};
int sz = sizeof(arr)/sizeof(arr[0]);
mergeSort(arr, tmp, 0, sz - 1);
for ( int i = 0; i < sz; ++i)
printf("%d ", arr[i]);
return 0;
}