一个TLE的代码:在最后一个测试点超时,十万个相同的数,因为全部相同的时候会退化到O(n^2)
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N];
int partition(int pivot,int l,int r)
{
while(l!=r)
{
while(a[l] <= pivot && l!=r )
{
l++;
}
if(l!=r)
{
swap(a[l],a[r]);
r--;
}
while(a[r] >= pivot && l!=r )
{
r--;
}
if(l!=r)
{
swap(a[l],a[r]);
l++;
}
}
return l;
}
int quick_sort(int l,int r)
{
if(l>=r) return 0;
int p=(l+r)>>1;//轴值的位置
int tem=a[p];
swap(a[p],a[r]);
int final_pos=partition(tem,l,r);//final_pos是最后轴值应该在的位置
a[final_pos]=tem;
quick_sort(l,final_pos-1);
quick_sort(final_pos+1,r);
return 0;
}
int main()
{
int n;
scanf("%d", &n);
for(int i = 0;i < n; i ++)
{
scanf("%d",&a[i]);
}
quick_sort(0,n-1);
for(int i = 0;i < n; i ++)
{
printf("%d ",a[i]);
}
return 0;
}
修改:
int partition(int pivot,int l,int r)
{
while(l!=r)
{
while(a[l] < pivot && l!=r )//修改a[l] <= pivot
{
l++;
}
if(l!=r)
{
swap(a[l],a[r]);
r--;
}
while(a[r] > pivot && l!=r )//修改a[l] >= pivot
{
r--;
}
if(l!=r)
{
swap(a[l],a[r]);
l++;
}
}
return l;
}