1 问题
是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法
2 分析过程
1 4 3 2 6 8 7 5 1 4 3 2 6 8 7 5 1 4 3 2 6 8 7 5 1 4 2 3 6 8 5 7 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
这里最关键的就是我们需要分析比如我们分治后变成了1 、4 和 2 、3这2部分数据，我们现在需要对这4个数排序，如果我们直接在这个数组里面操作下标对比，感觉分析起来很复杂，那我们可以借助辅助数组来分析，这个辅助数组的大小也是4，然后分别在2个数组1、4里面搞一个首指针，在2、3里面搞一个首指针，然后分别进行对比，然后小的数据放入辅助数组，哪个首指针插入辅助数组我么就向后移动，指导右一个手指针移动到尾巴，我们就结束比较，然后我们把右一个数组里面没有到尾巴的首指针再次移到尾巴，赋值给辅助数组就可以，然后我们辅助数组是排序好的元素，我们再把辅助元素里面的数据赋值给原数组。
1、 4 2、 3 i = start j = mid+1 end
对比数据时候循环终止条件
while (i != mid + 1 && j != end + 1) { }
3 代码实现
#include <stdio.h> void merge(int* source, int* temp, int start, int mid, int end) { if (source == NULL || temp == NULL) { printf("merge source or temp is NULL\n"); return; } int i = start, j = mid + 1, k = start; while (i != mid + 1 && j != end + 1) { if (source[i] > source[j]) temp[k++] = source[j++]; else temp[k++] = source[i++]; } while (i != mid + 1) temp[k++] = source[i++]; while (j != end + 1) temp[k++] = source[j++]; for(int h = start; h <= end; ++h) { source[h] = temp[h]; } } void mergeSort(int* source, int* temp, int start, int end) { if (source == NULL || temp == NULL) { printf("mergeSort source or temp is NULL\n"); return; } if (start < end) { int mid = start + (end - start) / 2; mergeSort(source, temp, start, mid); mergeSort(source, temp, mid + 1, end); merge(source, temp, start, mid, end); } } int main(void) { int source[] = {2, 3, 1, 5, 4, 9, 8, 6, 7}; int length = sizeof(source) / sizeof(int); int temp[9]; mergeSort(source, temp, 0, length - 1); for (int i = 0; i < length; ++i) { printf("%d\t", temp[i]); } return 0; }
4 运行结果
1 2 3 4 5 6 7 8 9