快排的最坏情况？想要避免除了一开始随机打乱还有什么好的办法？
面试遇到了这类问题，好像没找到什么特别好的办法...
2018-05-16 00:14 苏州大学 PHP
关注
全部评论
敲代码的咸鱼
南京大学 Java
返回值的时候返回两个数。等于最后一个数开始的位置与等于最后的一个数的位置
胶己人
吉林大学珠海学院 Java
主元取中位数，三向切分，快速三向切分，小数组使用插入排序，这些都是优化
BigRoc
东华大学 Java
在划分到N小于一定的数据值时 由于复杂度常数项的影响变得更加显著 可以使用其他算法替代
①苆茬①杺
南京邮电大学 Java
BFPRT 算法了解，这样的选择划分值好像比较好。
一路成长
东北大学 C++
块排最重要的就是partition()操作，如果是普通的快速排序，暂且叫partition(),可以采用随机区标志位进行划分；双路快排就是出现=标志位很多时，进行的优化；三路快排就是解决=标志位很多的情况。 具体partition()函数如下： template<typename T>
int __partion(T arr[],int l,int r)
{
int index=rand()%(r-l+1)+l;
swap(arr[l],arr[index]);
T temp=arr[l];
int j=l;
for(int i=l+1;i<=r;i++)
{
if(arr[i]<temp)
{
swap(arr[j+1],arr[i]);
j++;
}
}
swap(arr[l],arr[j]);
return j;
}
template<typename T> int __partion2(T arr[],int l,int r) { int index=rand()%(r-l+1)+l; swap(arr[l],arr[index]); T v=arr[l]; int i=l+1; int j=r; while(true) { while(i<=r&&arr[i]<=v) i++; while(j>l&&arr[j]>=v) j--; if(i<j) swap(arr[i++],arr[j--]); else break; } swap(arr[l],arr[j]); return j; } 三路快排就不写了，可以去看数据结构与算法。 其实排序算法中，到小范围的排序都可以采用插入排序，这也是一步优化。
汕大小吴
字节跳动_前端工程师
优化partition算法
木风feng
深圳大学 C++
STL的sort函数了解一下？
听风流水
北京邮电大学 Java
每次在取pivot时， 产生随机数去取~
Yu_Xiao
陕西科技大学 C++
三位取中？
相关推荐
查看20道真题和解析 点赞 评论 收藏
分享
查看6道真题和解析 点赞 评论 收藏
分享
点赞 评论 收藏
分享
查看10道真题和解析 点赞 评论 收藏
分享