快排之递归与非递归

前言

时间过得很快，今年就轮到我秋招找工作了，偶尔复习下常见的算法题并进行整理。方便自己后面复习，能给网友提供点参考也不错。

partition函数

该函数为快排的核心，思想就是在数组中找一个数作为中间值，把数组中比它小的放左边，大的放右边。这个函数有两种写法，单指针版和双指针版。下面给出C++代码：

//单指针分割 
int singlePartition(vector<int>& nums, int begin, int end){
int randIdx = rand()%(end-begin+1)+begin;
swap(nums[randIdx],nums[end]);
int index = begin;
for(int i = begin; i < end; ++ i){
if(nums[i]<=nums[end]) {
swap(nums[index++],nums[i]);
}
}
swap(nums[index],nums[end]);
return index;
}
//双指针分割 
int doublePartition(vector<int>& nums, int begin, int end){
int randIdx = rand()%(end-begin+1)+begin;
swap(nums[begin],nums[randIdx]);
int l = begin, r = end, x = nums[l];
while(l<r){
while(l<r&&nums[r]>=x) --r;
if(l<r&&nums[r]<x) swap(nums[r],nums[l]);
while(l<r&&nums[l]<=x) ++l;
if(l<r&&nums[l]>x) swap(nums[r],nums[l]);
}
nums[l] = x;
return l;
}

递归与非递归

递归版本就是对一组数据进行partition之后，对分界值的左半部分和右半部分分别进行相同操作，直到数组大小减到1停止。非递归版本其实就是用一个栈来保存左右边界下标，在栈弹空之前以栈顶两元素作为左右边界下标进行partition。思路都很简单，下面直接给出代码：

//递归版快排 
void recQsort(vector<int>& nums, int begin, int end){
if(begin>=end) return;
int mid = singlePartition(nums,begin,end);
recQsort(nums,begin,mid-1);
recQsort(nums,mid+1,end);
}
//非递归版快排
void Push(stack<int>& s, int left, int right){
s.push(left);
s.push(right);
}
void norecQsort(vector<int>& nums, int begin, int end){
stack<int> s;
Push(s,begin,end);
while(!s.empty()){
int r = s.top(); s.pop();
int l = s.top(); s.pop();
if(l>=r) continue;
int mid = singlePartition(nums,l,r);
Push(s,l,mid-1);
Push(s,mid+1,r);
}
}

最后

以上就是疯狂小刺猬为你收集整理的快排之递归与非递归的全部内容，希望文章能够帮你解决快排之递归与非递归所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。