排序

归并排序

归并思路：先分分到一个为止（单个默认有序），然后回溯排序。

如图（执行过程）：

	l=0,r=4,m=2，分为两组.
    l=0,r=2,m=1（上一组左分的继续左右分）,l=3,r=4,m=3（上一组右分的继续右分）
    l=0,r=1,m=0（上一组左分的继续左分，右分为一个了结束），（上一组右分结束）
    （左右分结束）（左右分结束）

单个时直接返回，如5,2单个返回到调用分它的上一层即（l=0,r=1,m=0）层，然后执行合并过程，，5,2进行排序，排序后重新复制到原数组（局部排序）。

5,2排序完后回到调用它的上一层（l=0,r=2,m=1）层，左右进行排序（两个有序数组的排序）。一次回溯直到解决。（倒数第二层就是两个有序数组的排序）。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    vector<int> MySort(vector<int>& arr) {
        // write code here
        msort(arr, 0, arr.size()-1);
        return arr;
    }
    void msort(vector<int>& v,int l,int r){
        if(l>=r)return;//单个默认排序
        int m = (l+r)/2;
        msort(v,l,m);//左分
        msort(v, m+1,r);//右分
        vector<int> t;
        int i = l,j = m + 1;
        while(i <= m && j <= r){
            if(v[i] <= v[j]) // 稳定算法
                t.push_back(v[i++]);
            else
                t.push_back(v[j++]);
        }
        while(i <= m)t.push_back(v[i++]);
        while(j <= r)t.push_back(v[j++]);
        for(int k = 0;k < t.size();++k)
            v[l++] = t[k];
    }
};

快排

思路：先排（找到基准），再左右分快排。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    vector<int> MySort(vector<int>& arr) {
        // write code here
        qsort(arr, 0, arr.size()-1);
        return arr;
    }
    void qsort(vector<int>& v,int l,int r){
        if(l >= r)return;
        int tmp = v[l];
        int i = l,j = r;
        while(i < j){
         // 由左右两个等于看出不稳定算法（等于的值移动过）
            while(i < j && v[j] >= tmp)//找到右边第一个比它小的
                --j;
            v[i] = v[j];
            while(i < j && v[i] <= tmp)//找到左边第一个比它大的
                ++i;
            v[j] = v[i];
        }
        v[i] = tmp;
        qsort(v,l,i-1);
        qsort(v,i+1,r);
    }
};