分治排序的应用

1. 归并排序题目链接https://www.luogu.com.cn/problem/P1177#ide#includebits/stdc.husingnamespacestd;// 传入 l, mid, r 明确告诉 merge 函数要合并哪两段voidmerge(vectorinta,intl,intmid,intr,vectorinttemp){intil;// 左半边起点intjmid1;// 右半边起点intkl;// 临时数组写入起点// 比较两半元素while(imidjr){if(a[i]a[j])temp[k]a[i];elsetemp[k]a[j];}// 拷贝剩余元素while(imid)temp[k]a[i];while(jr)temp[k]a[j];// 写回原数组for(intml;mr;m){a[m]temp[m];}}voidmergeSort(vectorinta,intl,intr,vectorinttemp){if(lr)return;intmidl(r-l)/2;mergeSort(a,l,mid,temp);// 1. 排左边 [l, mid]mergeSort(a,mid1,r,temp);// 2. 排右边 [mid 1, r]merge(a,l,mid,r,temp);// 3. 把 [l, mid] 和 [mid 1, r] 合并}intmain(){// 提升 cin/cout 读取效率可选但对于洛谷等 OJ 可以防止超时ios::sync_with_stdio(false);cin.tie(nullptr);intn;if(!(cinn))return0;vectorinta(n);for(inti0;in;i){cina[i];}// 开辟辅助数组 temp大小与原数组一致vectorinttemp(n);// 调用归并排序传入区间 [0, n - 1] 和辅助数组 tempmergeSort(a,0,n-1,temp);// 输出排序后的数组数字间用空格隔开for(inti0;in;i){couta[i](in-1?: );}cout\n;return0;}2. 数组中的逆序对剑指 Offer 51题目链接https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/classSolution{public:intmerge(vectorintrecord,vectorinttemp,intleft,intright,intmid){intileft;intjmid1;intkleft;intcount0;while(imidjright){if(record[i]record[j]){temp[k]record[i];}else{countmid-i1;temp[k]record[j];}}while(imid){temp[k]record[i];}while(jright){temp[k]record[j];}for(intileft;iright;i){record[i]temp[i];}returncount;}intmergeSort(vectorintrecord,vectorinttemp,intleft,intright){if(leftright){return0;}intmid(leftright)/2;intcountmergeSort(record,temp,left,mid)mergeSort(record,temp,mid1,right);countmerge(record,temp,left,right,mid);returncount;}public:intreversePairs(vectorintrecord){if(record.empty())return0;vectorinttemp(record.size());returnmergeSort(record,temp,0,record.size()-1);}};3. 最大子数组和题目链接https://leetcode.cn/problems/maximum-subarray/description/#includevector#includealgorithmusingnamespacestd;classSolution{structStatus{intlSum;// 以左端点起的最大连续和intrSum;// 以右端点结尾的最大连续和intmSum;// 区间内的最大连续和intiSum;// 区间总和};// 合并左右两个区间的信息StatuspushUp(constStatusL,constStatusR){intiSumL.iSumR.iSum;intlSummax(L.lSum,L.iSumL.rSum);intrSummax(R.rSum,R.iSumL.rSum);intmSummax({L.mSum,R.mSum,L.rSumL.lSum});return{lSum,rSum,mSum,iSum};}// 分治递归求解StatusgetStatus(vectorintnums,intl,intr){if(lr){return{nums[l],nums[l],nums[l],nums[l]};}intmidl(r-l)/2;Status leftStatusgetStatus(nums,l,mid);Status rightStatusgetStatus(nums,mid1,r);returnpushUp(leftStatus,rightStatus);}public:intmaxSubArray(vectorintnums){returngetStatus(nums,0,nums.size()-1).mSum;}};4. 最小 K 个数题目链接https://leetcode.cn/problems/smallest-k-lcci/description/classSolution{public:vectorintsmallestK(vectorintarr,intk){if(k0||arr.empty()){return{};}quickSelect(arr,0,arr.size()-1,k);returnvectorint(arr.begin(),arr.begin()k);}private:voidquickSelect(vectorintarr,intl,intr,intk){if(lr)return;// 随机选择 pivot 避免极端情况如退化为 O(N^2)intpivotIndexlrand()%(r-l1);swap(arr[pivotIndex],arr[r]);intipartition(arr,l,r);if(ik){return;// 已经找到了前 k 个小的元素排在 arr[0...k-1]}elseif(ik){quickSelect(arr,l,i-1,k);// 在左半部分继续寻找}else{quickSelect(arr,i1,r,k);// 在右半部分继续寻找}}intpartition(vectorintarr,intl,intr){intpivotarr[r];intil;for(intjl;jr;j){if(arr[j]pivot){swap(arr[i],arr[j]);i;}}swap(arr[i],arr[r]);returni;}};5. 数组中的第 K 个最大元素题目链接https://leetcode.cn/problems/kth-largest-element-in-an-array/description/classSolution{public:intfindKthLargest(vectorintnums,intk){returnquickSelect(nums,0,nums.size()-1,k);}private:intquickSelect(vectorintnums,intleft,intright,intk){if(leftright)returnnums[left];// 随机选择 pivot 避免极端退化intpivotIndexleftrand()%(right-left1);intpivotnums[pivotIndex];// 三路划分 ( 三方偏序 / Dutch National Flag )intlleft,ileft,rright;while(ir){if(nums[i]pivot){swap(nums[l],nums[i]);}elseif(nums[i]pivot){swap(nums[i],nums[r--]);}else{i;}}// 划分后区间分为// [left, l - 1] : 严格大于 pivot (个数为 bigCount)// [l, r] : 等于 pivot// [r 1, right] : 严格小于 pivotintbigCountl-left;intequalCountr-l1;if(kbigCount){// 第 k 大元素在大于 pivot 的部分returnquickSelect(nums,left,l-1,k);}elseif(kbigCountequalCount){// 第 k 大元素刚好等于 pivotreturnpivot;}else{// 第 k 大元素在小于 pivot 的部分更新 k 值returnquickSelect(nums,r1,right,k-bigCount-equalCount);}}};6. 快速排序#includeiostreamusingnamespacestd;// 快排函数对 arr[l] ~ arr[r] 排序voidquickSort(intarr[],intl,intr){if(lr)return;// 递归终止条件intpivotarr[l];// 选最左元素作为基准intil,jr;while(ij){// 右边找小于pivot的while(ijarr[j]pivot)j--;arr[i]arr[j];// 左边找大于pivot的while(ijarr[i]pivot)i;arr[j]arr[i];}arr[i]pivot;// 基准放到最终位置quickSort(arr,l,i-1);// 左区间递归quickSort(arr,i1,r);// 右区间递归}intmain(){inta[]{5,3,8,4,2,7,1,6};intnsizeof(a)/sizeof(a[0]);quickSort(a,0,n-1);for(inti0;in;i)couta[i] ;return0;}