归并排序的思路是 采用分治法,将一个大的问题拆分成若干个小问题,将一个大数组 拆为多个小数组进行排序 后再进去重组。 入下图锁示
拼合2个数组的思路:因为2个数组其实都是排过序的,只要给2个数组都设置个游标可以跟简单的进行组合。如下图所示
实现代码:
void _real_merge(int arr[], int start, int mid, int end) { int* temp = malloc(sizeof(int) * (end - start)); int start1 = start; int start2 = mid; int length = 0; while(1) { //两侧都用完 if(start1>=mid && start2 >= end) { break; } //有一侧的元素已经用完 else if(start1>=mid) { temp[length++] = arr[start2]; start2++; } else if(start2 >= end) { temp[length++] = arr[start1]; start1++; } //后大 else if(arr[start1] <= arr[start2]) { temp[length++] = arr[start1]; start1++; } //前大 else if(arr[start1] > arr[start2]) { temp[length++] = arr[start2]; start2++; } } //赋值回原来数组 for (int j = start; j<end; j++) { arr[j] = temp[j-start]; } free(temp); } void sort_merge(int arr[],int start, int end) { if(start == end - 1 ) { return; } int partCount = (end - start)/2; sort_merge(arr, start, start + partCount); sort_merge(arr, start + partCount, end); _real_merge(arr, start, start + partCount, end); } int arr[] = {8,4,5,7,1,3,6,2}; int len= (sizeof(arr) / sizeof(int)); sort_merge(arr, 0, len);
参考文章和图片引用链接:
http://www.cnblogs.com/chengxiao/p/6194356.html
没事就来转一转,每天多吃两碗饭!