MergeSort(归并排序)—人工智能导论 1.MergeSort原理
mergeSort的准备是sort，关键是 merge。
如何归并排序？它是分两步走的。
首先要把所给的数组分割开来，然后对分割开来的子数组进行合并。
看图比较容易理解：
2.MergeSort过程分析
经过我们的演示可以发现，我们的合并是沿着当初分割的原路合并的，在合并的时候将元素的大小顺序排好。
1.$textcolor{mediumorchid}{拆分} $ 将数组从中间分开得到新的两子数组，对子数组重复进行分割操作，把一整个数组通过递归的方法分成1/2、1/4、1/8 … 直到把数组分成许多个元素为1的子数组块。然后原路返回进行合并操作。
2.$textcolor{ForestGreen}{归并} $ 当需要合并的两个子数组都只有一个元素时，比较大小，谁小谁在前，谁大谁在后，按照小在前大在后的顺序加入到临时数组中。
当需要合并的两个子数组元素大于1 时，假如两个子数组为left[i] 、 right[j]，先使用两个数组的第一个元素比较大小，例如left[0]和right[0]比较大小，如果left[0] 如过left[] 的元素已经全部假如新的数组，而right[]还没有全部假如新数组，则之间将right[]的剩余元素按其本身的顺序关系添加到新数组后面即可，反之同理。
3.重复合并操作，直至重新生成的数组和数组大小一样，MergeSort结束。
3.代码实现
#includeusing namespace std;int MAXSIZE=15;//归并 void merging(int *list1,int list1_size,int *list2,int list2_size ){int tmp[MAXSIZE];int i,j,k;i=j=k=0;while(i < list1_size && j < list2_size){if(list1[i] < list2[j]){tmp[k++] = list1[i++];}else{tmp[k++] = list2[j++];}} // 如果比较的连个子数组中一个已经为空，另一个还有剩余元素，则直接追加到合并数组的后面while(i < list1_size){tmp[k++]=list1[i++];}while(j < list2_size){tmp[k++]=list2[j++];}for(int n = 0;n < (list1_size+list2_size);n++){list1[n] = tmp[n];} }//拆分 void mergesort(int arr[],int n){if(n>1){int *list1 = arr; // 指针指向左边子数组的第一个元素 int list1_size = n/2;int *list2 = arr+list1_size; // 指针指向右边边子数组的第一个元素 int list2_size = n-list1_size;//拆分 mergesort(list1,list1_size); // 对左半边数组继续做拆分 mergesort(list2,list2_size);// 对左半边数组继续做拆分 //归并 merging(list1,list1_size,list2,list2_size); // 对分开的数组进行合并操作}}int main(){int a[10]={1,3,6,8,0,9,4,2,5,7};printf("perpare sort array is "); for(int i = 0;i < 10;i++){printf("%d ",a[i]); // 1 3 6 8 0 9 4 2 5 7}printf("n");mergesort(a,10);printf("MergeSorted array is ");for(int i = 0;i < 10;i++){printf("%d ",a[i]); // 0 1 2 3 4 5 6 7 8 9}}