文章目录前言一、快速排序的习题讲解1. 排序数组模板题详细介绍快排算法的优化过程2. 数组中的第K个最大元素快速选择算法3. 练习题库存管理 III二、归并排序的习题讲解1. 排序数组模板题归并排序的算法思路2. 数组中的逆序对hard3. 计算右侧小于当前元素的个数前言快速排序 和 归并排序的算法思路详见【算法】常见排序算法插入排序、选择排序、交换排序和归并排序一、快速排序的习题讲解1. 排序数组模板题详细介绍快排算法的优化过程912. 排序数组题目描述给你一个整数数组 nums请你将该数组升序排列。你必须在 不使用任何内置函数 的情况下解决问题时间复杂度为 O(nlog(n))并且空间复杂度尽可能小。示例 输入nums [5,1,1,2,0,0]输出[0,0,1,1,2,5]解释请注意nums 的值不一定唯一。提示1 nums.length 5 * 10^4-5 * 10^4 nums[i] 5 * 10^4代码示例classSolution{public:voidswap(int*a,int*b){inttmp*a;*a*b;*btmp;}// 使用三数取中法选择三者的中位数作为基准值并将其换到begin位置voidmedian_select(vectorintvec,intbegin,intend){intmidbegin(end-begin)/2;if(vec[begin]vec[mid])// 目标: vec[mid] vec[begin]swap(vec[begin],vec[mid]);if(vec[mid]vec[end])// 目标: vec[end] vec[mid]swap(vec[mid],vec[end]);// 前两步使vec[end]位置一定是最大值if(vec[begin]vec[mid])// 目标: vec[begin] vec[mid]swap(vec[begin],vec[mid]);// 再从begin 和 end位置选出一个大的值放在begin位置// begin位置上保存这三个位置中间的值后续依然可以选第一个元素为基准值划分函数}// 采用三路划分的快速排序voidquicksort(vectorintnums,intbegin,intend){median_select(nums,begin,end);intkeynums[begin];intleftbegin;intrightend;intcurbegin1;while(curright){if(nums[cur]key){swap(nums[left],nums[cur]);left;cur;}elseif(nums[cur]key){swap(nums[right],nums[cur]);right--;}elseif(nums[cur]key)cur;}if(beginleft-1)quicksort(nums,begin,left-1);if(right1end)quicksort(nums,right1,end);}vectorintsortArray(vectorintnums){if(nums.size()1)quicksort(nums,0,nums.size()-1);returnnums;}};2. 数组中的第K个最大元素快速选择算法215. 数组中的第K个最大元素题目描述给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。示例1 输入[3, 2, 1, 5, 6, 4], k 2输出5示例2 输入[3, 2, 3, 1, 2, 4, 5, 5, 6], k 4输出4提示1 k nums.length 10^5-10^4 nums[i] 10^4代码演示classSolution{public:voidswap(int*a,int*b){inttmp*a;*a*b;*btmp;}// 使用三数取中法选择三者的中位数作为基准值并将其换到begin位置voidmedian_select(vectorintvec,intbegin,intend){intmidbegin(end-begin)/2;if(vec[begin]vec[mid])// 目标: vec[mid] vec[begin]swap(vec[begin],vec[mid]);if(vec[mid]vec[end])// 目标: vec[end] vec[mid]swap(vec[mid],vec[end]);// 前两步使vec[end]位置一定是最大值if(vec[begin]vec[mid])// 目标: vec[begin] vec[mid]swap(vec[begin],vec[mid]);// 再从begin 和 end位置选出一个大的值放在begin位置// begin位置上保存这三个位置中间的值后续依然可以选第一个元素为基准值划分函数}// 采用三路划分的快速排序intquicksort(vectorintnums,intbegin,intend,intk){median_select(nums,begin,end);intkeynums[begin];intleftbegin;intrightend;intcurbegin1;while(curright){if(nums[cur]key){swap(nums[left],nums[cur]);left;cur;}elseif(nums[cur]key){swap(nums[right],nums[cur]);right--;}elseif(nums[cur]key)cur;}intaleft-begin;// 小于key的元素个数intbright-left1;// 等于key的元素个数intcend-right;// 大于key的元素个数if(ck)returnquicksort(nums,right1,end,k);elseif(bck)returnkey;elsereturnquicksort(nums,begin,left-1,k-b-c);}intfindKthLargest(vectorintnums,intk){returnquicksort(nums,0,nums.size()-1,k);}};3. 练习题库存管理 IIILCR 159. 库存管理 III题目描述仓库管理员以数组 stock 形式记录商品库存表其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量返回 顺序不限。示例1 输入stock [2, 5, 7, 4], cnt 1输出[2]示例2 输入stock [0, 2, 3, 6], cnt 2输出[0, 2] 或 [2, 0]提示0 cnt stock.length 100000 stock[i] 10000二、归并排序的习题讲解1. 排序数组模板题归并排序的算法思路912. 排序数组题目描述给你一个整数数组 nums请你将该数组升序排列。你必须在 不使用任何内置函数 的情况下解决问题时间复杂度为 O(nlog(n))并且空间复杂度尽可能小。示例 输入nums [5,1,1,2,0,0]输出[0,0,1,1,2,5]解释请注意nums 的值不一定唯一。提示1 nums.length 5 * 10^4-5 * 10^4 nums[i] 5 * 10^4代码演示classSolution{public:// 归并排序voidmerge_sort(vectorintvec,intbegin,intend,vectorinttmp){intmidbegin(end-begin)/2;if(beginmid)merge_sort(vec,begin,mid,tmp);if(mid1end)merge_sort(vec,mid1,end,tmp);intleft1begin;intright1mid;intleft2mid1;intright2end;intindexbegin;while(left1right1left2right2){if(vec[left1]vec[left2]){tmp[index]vec[left1];index,left1;}else{tmp[index]vec[left2];index,left2;}}while(left1right1){tmp[index]vec[left1];index,left1;}while(left2right2){tmp[index]vec[left2];index,left2;}while(beginend){vec[begin]tmp[begin];begin;}}vectorintsortArray(vectorintnums){if(nums.size()1){vectorinttmp(nums.size());merge_sort(nums,0,nums.size()-1,tmp);}returnnums;}};2. 数组中的逆序对hardLCR 170. 交易逆序对的总数题目描述在股票交易中如果前一天的股价高于后一天的股价则可以认为存在一个「交易逆序对」。请设计一个程序输入一段时间内的股票交易记录 record返回其中存在的「交易逆序对」总数。示例 1输入record [9, 7, 5, 4, 6]输出8解释交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。提示0 record.length 50000classSolution{public:// 归并排序 增加第 5 个参数count_total统计逆序对的个数voidmerge_sort(vectorintarr,intbegin,intend,vectorinttmp,longlong*count_total){intmidbegin(end-begin)/2;if(beginmid)merge_sort(arr,begin,mid,tmp,count_total);if(mid1end)merge_sort(arr,mid1,end,tmp,count_total);intleft1begin;intright1mid;intleft2mid1;intright2end;intnbegin;while(left1right1left2right2){if(arr[left1]arr[left2]){tmp[n]arr[left1];}else// 在归并排序的过程中统计满足条件的逆序对个数{*count_totalright1-left11;tmp[n]arr[left2];}}while(left1right1){tmp[n]arr[left1];}while(left2right2){tmp[n]arr[left2];}while(beginend){arr[begin]tmp[begin];begin;}}intreversePairs(vectorintrecord){longlongcount0;if(record.size()2)return0;vectorinttmp(record.size());merge_sort(record,0,record.size()-1,tmp,count);returncount;}};3. 计算右侧小于当前元素的个数315. 计算右侧小于当前元素的个数题目描述给你一个整数数组 nums 按要求返回一个新数组 counts 。数组 counts 有该性质 counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。示例 1输入nums [ 5, 2, 6, 1 ]输出[ 2, 1, 1, 0 ]解释5 的右侧有 2 个更小的元素 (2 和 1)2 的右侧仅有 1 个更小的元素 (1)6 的右侧有 1 个更小的元素 (1)1 的右侧有 0 个更小的元素示例 2输入nums [-1]输出[0]示例 3输入nums [-1, -1]输出[0, 0]提示1 nums.length 10^5-10^4 nums[i] 10^4代码示例classSolution{public:voidmerge_sort(vectorintarr,intbegin,intend,vectorinttmp,vectorvectorintindex,vectorintret){intmidbegin(end-begin)/2;if(beginmid)merge_sort(arr,begin,mid,tmp,index,ret);if(mid1end)merge_sort(arr,mid1,end,tmp,index,ret);intleft1begin;intright1mid;intleft2mid1;intright2end;intnbegin;while(left1right1left2right2){if(arr[left1]arr[left2])// 在归并排序的过程中统计满足条件的逆序对个数{index[1][n]index[0][left1];ret[index[1][n]]right2-left21;// 增加对应下标 的逆序对个数tmp[n]arr[left1];}elseif(arr[left1]arr[left2]){index[1][n]index[0][left2];tmp[n]arr[left2];}}while(left1right1){index[1][n]index[0][left1];tmp[n]arr[left1];}while(left2right2){index[1][n]index[0][left2];tmp[n]arr[left2];}while(beginend){arr[begin]tmp[begin];index[0][begin]index[1][begin];begin;}}vectorintcountSmaller(vectorintnums){if(nums.size()1)returnvectorint(1,0);vectorintret(nums.size(),0);// 要对 index数组进行归并排序也需要一个临时数组// 所以直接创建两个数组index[1]作为下标绑定数组index[2]作为临时数组vectorvectorintindex(2,vectorint(nums.size()));for(inti0;inums.size();i){index[0][i]i;}vectorinttmp(nums.size());merge_sort(nums,0,nums.size()-1,tmp,index,ret);returnret;}};