排序——归并排序

归并排序的思想来源于合并两个已排好序的有序表。如果A、B分别是两张待归并的表，由于A、B都是有序的，因此只要从两表的表头开始：顺序比较表头元素，小者移人另一表C中。反复如此，直至其中一表为空为止，将另一表中剩余元素自左至右复制到表C的剩余位置。

#include <iostream>
#include <vector>
using namespace std;

//leftPos为子数组最左元素的下标
//rightPos为后半部分的起点下标
//rightEnd为子数组最右元素的下标
template<class T>
void merge(vector<T> &a, vector<T> &tmpVector, int leftPos, int rightPos, int rightEnd)
{
    int leftEnd = rightPos - 1;
    int tmpPos = leftPos;
    int num = rightEnd - leftPos + 1;

    while(leftPos <= leftEnd && rightPos <= rightEnd){
        if(a[leftPos] <= a[rightPos])
            tmpVector[tmpPos++] = a[leftPos++];
        else
            tmpVector[tmpPos++]= a[rightPos++];
    }

    while(leftPos <= leftEnd){ //复制前半部分的剩余元素
        tmpVector[tmpPos++] = a[leftPos++];
    }
    while(rightPos <= rightEnd){ //复制后半部分的剩余元素
         tmpVector[tmpPos++]= a[rightPos++];
    }

    for(int i = 0; i < num; ++i, --rightEnd){
        a[rightEnd] = tmpVector[rightEnd];
    }
}

template<class T>
void mergeSort(vector<T> &a, vector<T> &tmpVector, int left, int right)
{
    if(left < right){
        int center = (left + right) / 2;
        mergeSort(a, tmpVector, left, center);
        mergeSort(a, tmpVector, center + 1, right);
        merge(a, tmpVector, left, center + 1, right);
    }
}

template<class T>
void mergeSort(vector<T> &a)
{
    vector<T> tmpVector(a.size());
    mergeSort(a, tmpVector, 0, a.size() - 1); //传入的是下标
}


int main()
{
    vector<int> a = {9,8,7,6,5,4,3,2,1};

    mergeSort(a);

    for(int i = 0; i < a.size(); ++i)
        cout << a[i] << '\t' ;

    return 0;
}

假设N是2的幂，从而我们总可以将它分裂成相等的两部分。对于N=1，归并排序所用时间是常数，我们将其记为1。否则，对N个数归并排序的用时等于完成两个大小为N/2的递归排序所用的时间再加上合并的时间，后者是线性的。下述方程给出准确的表示： $$ \begin{array}{c}{T(1)=1} \ {T(N)=2 T(N / 2)+N}\end{array} \ \frac{T(N)}{N}=\frac{T(N / 2)}{N / 2}+1 \ \begin{aligned} \frac{T(N / 2)}{N / 2} &=\frac{T(N / 4)}{N / 4}+1 \ \frac{T(N / 4)}{N / 4} &=\frac{T(N / 8)}{N / 8}+1 \ & \vdots \ \frac{T(2)}{2} &=\frac{T(1)}{1}+1 \end{aligned} $$ 消去后可得： $$ \frac{T(N)}{N}=\frac{T(1)}{1}+\log N $$ 所以得到： $$ T(N)=N \log N+N=O(N \log N) $$

典型题目：

• 一本通 1311：【例2.5】求逆序对
• LeetCode 面试题 10.01. 合并排序的数组（从末尾开始比较）