排序（插入，冒泡，快速，归并，堆）

快速：

class Solution {
public:
    vector<int> MySort(vector<int>& arr) {
        // write code here
        quickSort(arr,0,arr.size()-1);
        return arr;
    }
    void quickSort(vector<int> &a,int left,int right){
        if(left >= right) return ;
        int point = partition(a, left, right);
        quickSort(a,left,point - 1);
        quickSort(a,point + 1, right);
    }
    int partition(vector<int> &a, int left, int right){
        int first = a[left];
        while(left < right){
            while(left < right && a[right] >= first) right--; 
            swap(a[right],a[left]); // 不大于基准first 交换放在前面。
            while(left < right && a[left] <= first) left++;
            swap(a[left],a[right]); // 不小于基准的 交换放在后面。
        }
        return left;
    }
};

冒泡：

void BubbleSort(vector<int> &a, int length){
   for(int i = 0; i < length; i++){ // i...    j
       int flag = 1; // 为1代表没发生移动
       for(int j = length -1 ; j > i; j--){  // n-1 到 i+1
           if(a[j-1]>a[j]){ swap(a[j-1],a[j]);flag = 0; } // 当前位置比前面小，交换且发生移动
       }
       if(flag) return;
   }
}

插入：

void InsertSort(vector<int> &a, int length){
      for(int i =1;i<length;i++){
          int tmp = a[i],j; // tmp 记录当前要插入的值
          for(j = i-1;j>=0&&a[j]>tmp;j--) a[j+1]=a[j]; // 当前值大于tmp 往后面移动 直到找一个小于tmp的位置
          a[j+1] = tmp; // 在当前值后面加入tmp。
      }
}

归并：

void mergeSort(vector<int> &a,int left, int right){
        if(left>=right)return;
        int mid = left+(right-left)/2;
        mergeSort(a,left,mid); // 左边排好序
        mergeSort(a,mid+1,right); // 右边排好序
        merge_(a,left,mid,right); // 左右两边合并
    }
    void merge_(vector<int> &a,int left,int mid,int right){
        vector<int> tmp(right-left+1);int t=0;  // 声明一个需要和排序元素一样大小的临时vector
        int l1=left,l2=mid+1;
        while(l1<=mid && l2<=right){  //将两个有序数组中元素最小的放入tmp ，一直到任意一个数组为空
            if(a[l1]<a[l2]) tmp[t++]=a[l1++];
            else tmp[t++] = a[l2++];
        }
        while(l1<=mid)tmp[t++] = a[l1++]; // 将为放入tmp的数放入进去。只会执行一个
        while(l2<=right)tmp[t++] = a[l2++];
        for(int i =0;i<t;i++){ // 将tmp复制到a的指定位置。
            a[left+i] = tmp[i]; 
        }
    }

优先队列类似堆排序：

  vector<int> MySort(vector<int>& arr) {
        vector<int> ans(arr.size());
        priority_queue<int> qu; // 默认大根堆，优先输出最大值。
        for(int x:arr) {qu.push(x);}
        for(int i =ans.size()-1;i >=0;i--){
            ans[i]=qu.top();
            qu.pop();
        }
        return ans;
    }