快排（必备）+归并（体会分治）+堆(自己建堆)

//快速排序 关键在于 partition函数，可以自己参考一个模板，我这个参考大话数据结构

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    //1.快速排序
    vector<int> MySort(vector<int>& arr) {

        int start=0;
        int end=arr.size()-1;

        MySortCore(arr,start,end);
        return arr;
    }
    void MySortCore(vector<int>&arr,int start,int end){
        if(start<end){
            int pivot=partiton(arr,start,end);
            MySortCore(arr,start,pivot-1);
            MySortCore(arr,pivot+1,end);
        }

    }
    int partiton(vector<int>&arr,int start,int end){
        int left=start;
        int right=end;
        int pivotKey=arr[left];

        while(left<right){
            while(left<right && arr[right]>=pivotKey)
                --right;
            arr[left]=arr[right];

            while(left<right && arr[left]<=pivotKey)
                ++left;
            arr[right]=arr[left];
        }
        arr[left]=pivotKey;

        return left;
    }
};

//归并排序 关键在于构造一个数组 然后merge，所以这个 merge函数是关键
class Solution {
public:
    //归并排序
    vector<int> MySort(vector<int>& arr) {
        MySortCore(arr,0,arr.size()-1);


        return arr;
    }
    void MySortCore(vector<int>&arr,int start,int end){
        if(start>=end) return;

        int middle=start+((end-start)>>1);
        MySortCore(arr,start,middle);
        MySortCore(arr,middle+1,end);

        Merge(arr,start,middle,end);
    }
    void Merge(vector<int>&arr,int start,int middle,int end){
        int* tmp=new int[end-start+1];

        int left=start;
        int right=middle+1;

        int pTmp=0;    //辅助数组指针
        while(left<=middle && right<=end){
            if(arr[left]<arr[right])
                tmp[pTmp++]=arr[left++];
            else
                tmp[pTmp++]=arr[right++];

        }
        while(left<=middle)
            tmp[pTmp++]=arr[left++];
        while(right<=end)
            tmp[pTmp++]=arr[right++];

        //排序完数组拷贝回原数组
        for(int i=0;i<end-start+1;i++)
            arr[start+i]=tmp[i];

    }
};
//堆排序，分为两步，建堆+排序
//一些细节可以参考大话数据结构
//我这个堆是从下标为0开始的，所以左子节点 left=2*root+1, right=2*root+1

class Solution {
public:
    //堆排序
    void Swap(int&a,int &b){
        int tmp=a;
        a=b;
        b=tmp;
    }
    void HeapAdjust(vector<int>&arr,int root,int len){
        int tmp=arr[root];

        for(int j=2*root+1;j<len;j=2*j+1){
            if(j<len-1 && arr[j]<arr[j+1])
                ++j;
            if(tmp>arr[j])
                break;
            arr[root]=arr[j];
            root=j;
        }
        arr[root]=tmp;

    }
    vector<int> MySort(vector<int>& arr) {
        for(int i=arr.size()/2-1;i>=0;i--)
            HeapAdjust(arr,i,arr.size());

        for(int i=arr.size()-1;i>0;i--){
            Swap(arr[0],arr[i]);
            HeapAdjust(arr,0,i);
        }

        return arr;
    }
};