2017优秀网站设计欣赏,有没有做兼职的网站,mip网站有什么好处,常州公司网站建设本章我们要学习的是分治算法#xff0c;顾名思义就是分而治之#xff0c;把大问题分为多个相同的子问题进行处理#xff0c;其中我们熟知的快速排序和归并排序用的就是分治算法#xff0c;所以我们需要重新回顾一下这两个排序。
一、快速排序#xff08;三路划分#xf… 本章我们要学习的是分治算法顾名思义就是分而治之把大问题分为多个相同的子问题进行处理其中我们熟知的快速排序和归并排序用的就是分治算法所以我们需要重新回顾一下这两个排序。
一、快速排序三路划分
1.算法思想 首先从数列中确定一个需要排序的数记为key把所有key排到它的正确位置即排序后它的位置然后同样的方法使用递归分治思想把小于key的区间与大于key的区间进行排序直到这个区间不存在或只有一个元素时返回。 具体方法从左到右遍历数组并且我们使用三个变量leftmidright把数组划分为四个区间分别表示小于key等于key未遍历大于key。而mid位置就是此时遍历到的数判断这个数与key的关系然后把它放在对应的区间。再用同样方法将大于key和小于key的区间排序。 注意在此快速排序我使用了三路划分的优化方法和对key取用随机值这样比普通的快速排序效率要高得多而且是一种很实用的分治算法。
2.代码实现 vectorint sortArray(vectorint nums){srand((unsigned int)time(NULL));dfs(0,nums.size()-1,nums);return nums;}void dfs(int n,int m,vectorint nums){if(nm) return;int keynums[nrand()%(m-n1)];int leftn-1,rightm1,midn;while(midright){if(nums[mid]key) swap(nums[left],nums[mid]);else if(nums[mid]key) mid;else swap(nums[mid],nums[--right]);}dfs(n,left,nums);dfs(right,m,nums);}
二、归并排序
1.算法思想 对于一个乱序的数组我们可以把一分为二先让两个小数组有序然后再将它们合并。那么如何让这两个小数组有序呢同样的可以把它们分别再拆开变成四个小组然后继续一直往下拆直到拆到只有一个元素那么它必然是有序的最后进行一一合并这整个的思路有点像二叉树的后续遍历。 2.代码实现 vectorint tmp;vectorint sortArray(vectorint nums){tmp.reserve(nums.size());dfs(0,nums.size()-1,nums);return nums;}void dfs(int left,int right,vectorint nums){if(leftright) return;int mid(leftright)1;dfs(left,mid,nums);dfs(mid1,right,nums);int p1left,p2mid1;int ileft;while(p1midp2right)tmp[i]nums[p1]nums[p2]?nums[p1]:nums[p2];while(p1mid) tmp[i]nums[p1];while(p2right) tmp[i]nums[p2];for(int jleft;jright;j) nums[j]tmp[j];}
对于快速排序和归并排序需要了解更多细节请参考下文
【排序算法】—— 快速排序_快速排序方法-CSDN博客
【排序算法】—— 归并排序-CSDN博客
三、快速选择算法 当我们看到这个题目的时候可能脑子里很快想到用堆解决TopK问题或者是使用排序来解决。 但这是一个面试题以上两种解决方法都不足以让我们拿到offer。需要注意题目描述是任意顺序返回这k个数而不是有序返回那么我们就应该意识到应该还有更优的解决方法。 对于使用堆和排序时间复杂度都为O(nlogn)而这个题我们可以用快速选择算法时间复杂度为O(n)这是由快速排序延伸出的一个算法。同样使用分治思想。
算法思想 class Solution {
public:vectorint smallestK(vectorint arr, int k){srand((unsigned int)time(NULL));dfs(0,arr.size()-1,arr,k);return {arr.begin(),arr.begin()k};}void dfs(int l,int r,vectorint arr,int k){if(lr) return;int keyarr[rand()%(r-l1)l];int leftl-1,rightr1,midl;while(midright){if(arr[mid]key) swap(arr[left],arr[mid]);else if(arr[mid]key) mid;else swap(arr[mid],arr[--right]);}int aleft-l1,bmid-left-1;if(ka) dfs(l,left,arr,k);else if(kab) return;else dfs(right,r,arr,k-a-b);}
};
四、逆序对问题 关于这个题最容易想到的就是暴力方法双重循环时间复杂度为O(n^2)毫无疑问是通过不了这个题的这个题我们可以利用归并排序来完成计数时间复杂度为O(nlogn)。
算法思想 class Solution {
public:int count0;vectorint tmp;int reversePairs(vectorint record) {tmp.reserve(record.size());dfs(0,record.size()-1,record);return count;}void dfs(int left,int right,vectorint nums){if(leftright) return;int mid(leftright)1;dfs(left,mid,nums);dfs(mid1,right,nums);int p1left,p2mid1;int ileft;while(p1midp2right){if(nums[p1]nums[p2]) tmp[i]nums[p1];else countmid-p11, tmp[i]nums[p2];}while(p1mid) tmp[i]nums[p1];while(p2right) tmp[i]nums[p2];for(int ileft;iright;i)nums[i]tmp[i];}
}; 非常感谢您能耐心读完这篇文章。倘若您从中有所收获还望多多支持呀
