内容分发网络CDN可以建设网站吗,备案的网站如何访问,成都网站建设公司创新互联,海报设计平台快速排序算法采用了分治法以及递归作为解决问题的思想。在计算机科学中#xff0c;分治法是一种很重要的算法。字面上的解释是“分而治之”#xff0c;就是把一个复杂的问题分成两个或更多的相同或相似的子问题#xff0c;再把子问题分成更小的子问题……直到最后子问题可以… 快速排序算法采用了分治法以及递归作为解决问题的思想。在计算机科学中分治法是一种很重要的算法。字面上的解释是“分而治之”就是把一个复杂的问题分成两个或更多的相同或相似的子问题再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解原问题的解即子问题的解的合并。快速排序算法算法思路快速排序算法的思路是先在arr[s,t]中随意选取一个点作为排序的基准点x再确定基准点在数组中的下标一定下标i确定后该下标i左边的所有元素均小于x右边的所有元素均大于x.此时采用递归继续对数组[s,i-1]以及[i1,t]做快速排序左右区间不再合法即可退出循环。分治的思想就体现在同时对基准点的左右区间再次做快速排序上。找基准点首先姑且认为区间左端的第一个元素就是基准点x再定义两个下标i与j分别记录区间的原始左端点与右端点先从右端点开始往左查找如果arr[j]x且ij,则j--,这样能够确保基准点右边的元素都大于或等于基准点若遇到arr[j]x,则将arr[j]放到基准点原来的位置紧接着下标i往右查找如果arr[i]x且ij,则i,这样能够保障基准点左边的元素都小于或等于基准点若遇到arr[i]x,则将arr[i]放到上次j的位置重复上述操作直到ij将基准点放在arr[i]上即arr[i]x.代码实现#includeiostream
using namespace std;
#includealgorithm//快速查找算法查找第k小的元素void quick_sort(int*arr,int l,int r){//递归退出条件if(lr){return ;}int i l;int j r;//以区间最左侧的元素最为基准点int x arr[l];//调整基准点while(ij){//找到一个比基准点小的数while(ij arr[j]x) j--;if(ij){//将arr[j]放到最左边arr[i] arr[j];} //找一个比基准点大的数while(ij arr[i]x) i;if(ij){arr[j] arr[i];}} arr[i] x;//调整基准点//对基准点的左区间排序quick_sort(arr,l,i-1);//对基准点的右区间排序quick_sort(arr,i1,r);
}
void Myprint(int val){coutval ;
}int main(){int arr[12]{10,2,1,3,6,5,4,7,9,8,42,99};int len sizeof(arr)/sizeof(int);quick_sort(arr,0,len-1);for_each(arr,arrlen,Myprint);coutendl;return 0;
}快速定位算法问题引入已知定长为len的int数组需要查出第k小的元素。算法思路借鉴快速排序的思路基准点必定大于或等于其左区间的元素小于或等于右区间的元素因此找到一个下标为k-1的基准点等价于找到第k小的元素。我们只需要在原快速排序算法删改一些代码即可获得快速排序算法的代码实现。代码实现#includeiostream
using namespace std;//快速查找算法查找第k小的元素int quick_select(int*arr,int l,int r, int k){int i l;int j r;//以区间左端点为基准点int x arr[l];//调整基准点while(ij){//找到一个比基准点小的数while(ij arr[j]x) j--;if(ij){//将arr[j]放到最左边arr[i] arr[j];} //找一个比基准点大的数while(ij arr[i]x) i;if(ij){arr[j] arr[i];}} arr[i] x;//调整基准点//判断基准点x的下标i是否与k-1相同if(ik-1) return arr[i];else if(ik-1)return quick_select(arr,i1,r,k);elsereturn quick_select(arr,l,i-1,k);
}int main(){int arr[12]{10,2,1,3,6,5,4,7,9,8,42,99};int k 12;int len sizeof(arr)/sizeof(int);coutquick_select(arr,0,len-1,k)endl;//答案无疑是99return 0;
}可见当ik-1时说明第k小的元素在基准点的右侧只需要再查找基准点的右侧区间当ik-1时说明第k小的元素在基准点的左侧只需要再查找基准点的左侧区间
