hdzattain-题解

class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型vector 待排序的数组
* @return int整型vector
*/
vector<int> MySort(vector<int>& arr) {
// write code here
Sort(arr,0,arr.size()-1);
return arr;
}
int Partition(vector<int> &arr,int low,int high){//合并
int i=low,k=high;
int temp = arr[low];//临时变量存low里的值
while(i<k){
while(i<k&& temp<=arr[k]) --k;//找到第一个小于temp的数字
if(i<k) arr[i++] = arr[k];//把它放在小端，i位置已经记录于temp
while(i<k&&arr[i]<=temp) ++i;//找到左边第一个大于temp的数字
if(i<k) arr[k--] = arr[i];//把他放在大端，k位置前面已经移动
}
arr[i] =temp;//放好temp
return i;
}
void Sort(vector<int> &arr,int low,int high){//拆分
if(low>=high)//base case
return ;
int pos = Partition(arr,low,high);
Sort(arr,low,pos-1);//左
Sort(arr, pos+1, high);//右
}
};
//一段用于加速的代码
static const auto io_sync_off = //这边不能加;分号，这是一个lambda函数
{
std::ios::sync_with_stdio(false);//关掉输入输出同步，解除流缓冲区，这时不能混用printf,scanf,cin,cout
std::cin.tie(nullptr);//nullptr是一个字面值常量，可以转换为任意类型的空指针，tie是将两个stream绑定函数，这里用空指针解除cin和cout的绑定，加速io
return nullptr;
}();</int></int></int></int>