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]<right[0],先则把left[0]为加入到临时数组中；left[1]再和right[0]比较大小。如此进行下去。
如过left[] 的元素已经全部假如新的数组，而right[]还没有全部假如新数组，则之间将right[]的剩余元素按其本身的顺序关系添加到新数组后面即可，反之同理。
3.重复合并操作，直至重新生成的数组和数组大小一样，MergeSort结束。
3.代码实现
#include<bits/stdc++.h>
using 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
}
}