双指针写法的快速排序的各种边界问题

https://www.acwing.com/problem/content/description/787/
1.枢纽元素是第l+r+1：

那么分割必须是l, i-1, i, r，为什么是i-1，因为++i ，跳出循环时是a[ i ]>=x的，所以左面函数的闭区间的右端点是i-1,当分割点是i时，枢纽元素不能取左端点，也就是a[ l ]，怎么处理见3。

#include <iostream>
#include <algorithm> 
using namespace std;
const int maxn=1e6+7;
int a[maxn],n;
void quicksort(int l,int r){
if(l>=r)return ;
int x=a[l+r+1>>1],i=l-1,j=r+1;
while(i<j){
while(a[++i]<x);
while(a[--j]>x);
if(i<j)swap(a[i],a[j]);
}
quicksort(l,i-1);
quicksort(i,r);
}
int main(){
scanf("%d",&n);
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
}
quicksort(1,n);
for(int i=1; i<=n; i++){
printf("%d ",a[i]);
}
return 0;
}

2.枢纽元素是l+r>>1：

细节问题同1，细节处理见4

#include <iostream>
#include <algorithm> 
using namespace std;
const int maxn=1e6+7;
int a[maxn],n;
void quicksort(int l,int r){
if(l>=r)return ;
int x=a[l+r>>1],i=l-1,j=r+1;
while(i<j){
while(a[++i]<x){
};
while(a[--j]>x){
};
if(i<j)swap(a[i],a[j]);
}
quicksort(l,j);
quicksort(j+1,r);
}
int main(){
scanf("%d",&n);
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
}
quicksort(1,n);
for(int i=1; i<=n; i++){
printf("%d ",a[i]);
}
return 0;
}

3.枢纽元素取左端点或者是l+r>>1能取到左端点时：

在while加个等于条件将死循环跳出，递归到下一个时，l>r会退出。–j最好加个条件j==l+1&&a[++j]>x，防止j越界到0，或者是负数。

#include <iostream>
#include <algorithm> 
using namespace std;
const int maxn=1e6+7;
int a[maxn],n;
void quicksort(int l,int r){
if(l>=r)return ;
int x=a[l+r>>1],i=l-1,j=r+1;
while(i<=j){
while(a[++i]<x){
};
while(a[--j]>x){
};
if(i<j)swap(a[i],a[j]);
}
quicksort(l,i-1);
quicksort(i,r);
}
int main(){
scanf("%d",&n);
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
}
quicksort(1,n);
for(int i=1; i<=n; i++){
printf("%d ",a[i]);
}
return 0;
}

4.枢纽元素取右端点或者是l+r+1>>1能取到右端点时：

这里多加的条件是必须的，否则i会加到很大的数，导致数组越界。

#include <iostream>
#include <algorithm> 
using namespace std;
const int maxn=1e6+7;
int a[maxn],n;
void quicksort(int l,int r){
if(l>=r)return ;
int x=a[l+r+1>>1],i=l-1,j=r+1;
while(i<=j){
while(i<=r-1&&a[++i]<x){
};
while(a[--j]>x){
};
if(i<j)swap(a[i],a[j]);
}
quicksort(l,j);
quicksort(j+1,r);
}
int main(){
scanf("%d",&n);
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
}
quicksort(1,n);
for(int i=1; i<=n; i++){
printf("%d ",a[i]);
}
return 0;
}

最后

以上就是勤恳时光最近收集整理的关于双指针写法的快速排序的各种边界问题的全部内容，更多相关双指针写法内容请搜索靠谱客的其他文章。