算法 — 归并排序

归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

下面通过示意图来说明这种步骤思想

1、每次排序的时候都将数组一分为二，同时申请同样大小的临时空间，这时候使用三个索引，k 是在归并过程中需要跟踪的位置，i 和 j 分别代表指向两个数组

2、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

3、较小的元素就比放到最终的数组中，追踪的位置 k++，同时较小的元素的那方 j++

4、重复步骤 2和3 直到某一指针达到序列尾

// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
template<typename  T>
void __merge(T arr[],int l,int mid,int r)
{
    //把传入来的arr数组，赋值给新建一个内存空间
    T temp[r-l+1];
    for(int i=l;i<=r;i++)
        temp[i-1] = arr[i];
    // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
    // i -- 左边索引
    // j -- 右边索引
    // k -- 正确排序数组索引
    int i = l; int j = mid+1;
    for(int k = l;k <= r;k++)
    {
        if( i > mid ){                      //如果左半部分元素已经全部处理完毕
            arr[k] = temp[j-l];             //剩下的只有右半部分按序排序
            j++;
        }
        else if( j > r ){                   //如果右半部分元素已经全部处理完毕
            arr[k] = temp[i-l];             //剩下的只有左半部分按序排序
            i++;
        }
        else if( temp[i-l] < temp[j-l] ) {  //右边部分索引的元素大于左边部分索引的元素
            arr[k] = temp[i-l];             //左边部分索引的元素 放在正确排序数组上
            i++;                           //排序完，左边部分索引往前一个
        }
        else{                               //左边部分索引的元素大于右边部分索引的元素
            arr[k] = temp[j-l];             //右边部分索引的元素 放在正确排序数组上
             j++;                          //排序完，右边部分索引往前一个
        }
    }
}

//递归使用并排序，对arr[l...r]的范围进行排序
template<typename T>
void __mergeSort(T 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, mid, r);
}

template<typename T>
void mergeSort(T arr[], int n)
{
    __mergeSort( arr , 0 , n-1 );
}