分治思想和算法

#例1《快速排序》##includeiostream using namespace std; void swap(int a,int b){//交换函数 int ta; ab; bt; return;//void可直接返回 } void quickSort(int a[],int left,int right){//传入数组左右边界可拓展为vector容器 if(leftright)return;//处理边界问题 int ileft,jright,pivota[left];//取left为基准值可以减小极端情况的影响 while(ij){//ij时弹出否则交换受影响 while(ij a[i]pivot)i; while(ij a[j]pivot)j--; if(ij)swap(a[i],a[j]); } swap(a[left],a[i]);//把基准值放在排序好的位置上 quickSort(a,left,i-1); quickSort(a,i1,right); return;//直接返回 }#快排优化版本#相当于是每次把valvec[i]放在排序好的位置上。int partation(vectorint vec,int i ,int j){//基准值与排序步骤 int valvec[i],li,rj; ifj-i50InsertSort(vec,i,j);#快排在最差情况下会退化到On**2时间复杂度 #插入排序的效率在数组有序的时候效率最高 while(lr){ while(lr vec[r]val)r--;//要小于等于否则容易卡死 if(lr)vec[l]vec[r];//也可以写成vec[l]vec[r];r--; while(lr vec[l]val)l; if(lr)vec[r--]vec[l]; } vec[l]val;//把基准值放在排序好的位置 return l;//返回基准位置便于下一步操作 }void quickSort(vectorint vec,int i, int j){ if(ij)return; int pospartation(vec,i,j); quickSort(vec,i,pos-1); quickSort(vec,pos1,j); return; }#例2求TOPk分治做法#int di_TOPk_big(vectorint vec, int i,int j,int k){ int pospartation(vec,i,j); if(posvec.size()-k)return pos; else if(posvec.size()-k)return di_TOPk_big(vec,pos1,j,k); else if(posvec.size()-k)return di_TOPk_big(vec,i,pos-1,k); }#归并排序分-治-合#时间复杂度O(n log n)。无论输入数据是否有序时间复杂度都稳定拆分过程是log n层每层合并操作是O(n)。空间复杂度O(n)。需要临时数组tmp存储合并结果。稳定性稳定排序。当两个元素相等时a[i] a[j]优先保留左子数组的元素不会改变相等元素的相对顺序。适用场景适合大规模数据排序尤其是外部排序如磁盘文件排序但因需要额外空间小规模数据可能不如插入排序高效。#includeiostream using namespace std; int a[1001], tmp[1001]; void mergesort(int l, int r) { if (l r)return; int mid (l r) / 2; mergesort(l, mid); mergesort(mid 1, r); merge(l, mid, r); }归并排序伪代码实现传入参数l左边界、r右边界设置退出条件lr退出设置中间的划分坐标mid(lr)/2划分区间左边是l-mid右边则是mid1-r设置合并区间实际上利用了tmp数组来存放排序好的数组所以需要同等空间大小的数组递归的逻辑每次调用函数都会开辟一个栈空间不断调用函数到最小也就是可以解决问题的时候就开始回溯后一个问题解决完了就解决前一个问题。所以就是从大划分到小再从小到大解决等都解决好才会释放空间。流程就是先不断划分成小区间划分到最小区间的时候不执行mergesort函数就开始合并合并好的部分存放在tmp数组中tmp的坐标区间和原数组是一样的。小的部分排序好了就会一步步解决更大的待排序函数。void merge(int l, int mid, int r) { int i l, j mid 1, k l; while(i mid j r) { if (a[i] a[j]) tmp[k] a[i]; else tmp[k] a[j]; } while (i mid)tmp[k] a[i]; while (j r)tmp[k] a[j]; for (int i l; i r; i)a[i] tmp[i]; }拟合并数组(a)0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9[ l mid ][ mid1 r ]i jtmp: kl;如果nums[i]nums[j]{把nums[i]放在tmp[k]的位置随后ik}否则{把nums[j]放在tmp[k]的位置随后jk}上面两个区间有一方分配完就退出循环把另一方的剩余元素直接补在k的末尾然后就排序好tmp数组【l到r】区间的元素了这时候在再把tmp数组【l到r区间】传给a数组由此就排序好一个区间了。非递归归并排序原理把原来的数组已经看作是分到了最小的区间每个区间只有一个元素开始合并。合并的时候从步长为1开始处理整个数组处理边界问题如果右边界超过了数组长度就把右边界定位最大数组长度如果左数组超过了数组长度那么本次无需合并它原本就是已经排序好的。不断循环每次步长是原来的两倍并且不超过数组最大下标最大步长不超过数组长度在大于数组长度一半的时候就已经是合二为一的最后一次合并了。void mergeSort(int n) { for (int step 1; step n; step * 2) { // 步长从1开始每次翻倍 for (int i 1; i n; i 2 * step) { // 每次处理两个step长度的子数组 int l i; int mid i step - 1; int r i 2 * step - 1; if (r n) r n; // 右边界不超过数组长度 if (mid n) continue; // 左子数组越界无需合并 merge(l, mid, r); } } }力扣题目寻找两个正序数组的中位数#include vector #include climits // 包含 INT_MIN 和 INT_MAX using namespace std; class Solution { public: double findMedianSortedArrays(vectorint nums1, vectorint nums2) { // 确保 nums1 是较短的数组优化二分查找效率 if (nums1.size() nums2.size()) { return findMedianSortedArrays(nums2, nums1); } int m nums1.size(); int n nums2.size(); int left 0, right m; // 二分查找 nums1 的分割点范围 while (left right) { // i 是 nums1 左侧的元素个数分割点 int i (left right) / 2; // j 是 nums2 左侧的元素个数总左侧元素为 (mn1)/2确保左侧比右侧多1个当总数为奇数时 int j (m n 1) / 2 - i; // 处理边界情况左侧无元素时用 INT_MIN 表示 int left1 (i 0) ? INT_MIN : nums1[i - 1]; int left2 (j 0) ? INT_MIN : nums2[j - 1]; // 处理边界情况右侧无元素时用 INT_MAX 表示 int right1 (i m) ? INT_MAX : nums1[i]; int right2 (j n) ? INT_MAX : nums2[j]; // 找到有效分割点左侧所有元素 右侧所有元素 if (left1 right2 left2 right1) { // 总长度为奇数时中位数是左侧最大值 if ((m n) % 2 1) return max(left1, left2); // 总长度为偶数时中位数是左侧最大值和右侧最小值的平均 else return (max(left1, left2) min(right1, right2)) / 2.0; } // 左侧过大需要减少 nums1 的左侧元素 else if (left1 right2) right i - 1; // 左侧过小需要增加 nums1 的左侧元素 else left i 1; } return 0.0; } };