【算法】归并排序算法

算法简介

  归并排序是一种将递归和分治结合到一起实现的一种排序算法。将一个序列通过递归拆分为越来越小的半子序列，然后再对半子序列合并为 一个大的有序序列。

算法思想

  归并排序算法可以分为递归和归并两部分。首先对一个序列进行递归，要将一个序列排序，先要将序列的前半部分排序，然后再将序列的后半部分，要排序前半部分又将前半部分分为两部分，依次递归。。。 当递归到一个元素的时候，不用排序，一个元素本身已经是有序的了。然后便是合并操作，将左右两个有序的序列合并为一个序列，然后一级一级递归，直到整个序列合并完成。

  归并排序图解如下：

代码示例

//将数组arr中[l,r]内的元素进行归并
void merge(int arr[], int l,int r)
{
    int* temp = (int*)malloc(sizeof(int)*(r-l+1));
    memcpy(temp,arr+l,sizeof(int)*(r-l+1));
    int middle = (l+r)/2;
    int indexl=l,indexr = middle+1;
    for(int i=l;i<=r;i++){
        if(indexl > middle){
            arr[i] = temp[indexr-l];
            indexr++;
        }else if(indexr > r){
            arr[i] = temp[indexl-l];
            indexl++;
        }else if(temp[indexl-l] > temp[indexr-l]){
            arr[i] = temp[indexr-l];
            indexr++;
        }else{
            arr[i] = temp[indexl-l];
            indexl++;
        }
    }
}

//将数组arr中的[l,r]区间内的元素进行排序
void MergeSort(int arr[], int l,int r)
{
    if(l>=r) return;
    int mid = (l+r)/2;
    MergeSort(arr,l,mid);
    MergeSort(arr,mid+1,r);
    merge(arr,l,r);
}