我最近才知道quicksort。我读到枢轴选择在整体表现中起着非常重要的作用。我有一个任务，我应该测试 3 种枢轴选择变体 -随机、3 的中位数和不同输入大小的中位数的中位数。我读过中位数版本的中位数即使在最坏的情况下也不会在 O(n2) 中运行。但在我的结果中，三个版本的随机化和中位数给出了几乎相似的结果，三个版本的中位数稍好一些，但中位数的中位数表现非常差几个数量级。例如，在输入大小为 50000 时，随机版本跑进来，16547 us而中位数的中位数跑进来1139168 us. 有人可以解释为什么会这样吗？（据我所知，我已经正确实现了枢轴选择算法——将数组分成 5 个一组，取每组的中位数，然后递归地再次执行此操作，直到我得到中位数。）我做错了什么吗？
编辑：为了以防万一，我正在重新检查代码，但是中位数实现的中位数是否正常工作与其他两个实现一样慢甚至更慢（如果只是轻微地），还是保证工作得更快？
Edit2：这是我用于查找中位数的代码，它找到的值将返回给快速排序函数以用作枢轴。我确信该代码违反了所有良好的编码实践，请将此归因于我的菜鸟，并尝试超越它。
int getpivot(int arr[], int low, int high) {
int i,j,k,l,val,med[MAX/4],temp[6],pivot,mi,index,temp2;
if(high-low+1<=5) { //returns median if size of array<=5
for(i=1;i<=high;i++) {
val=arr[i];
j=i-1;
while(j>=0 && val<arr[j]) {
arr[j+1]=arr[j];
j--;
}
arr[j+1]=val;
}
return arr[(low+high)/2];
}
mi=0;
// divide array into groups of 5,
//finds median of those groups by insertion sorting
//adds these medians to med array
for(i=low;i+5<=high;) {
index=0;
for(j=i;j<i+5;j++)
temp[index++]=arr[j];
i+=5;
for(k=1;k<5;k++) {
val=temp[k];
l=k-1;
while(l>=0 && temp[l]>val) {
temp[l+1]=temp[l];
l--;
}
temp[l+1]=val;
}
med[mi++]=temp[2];
}
//choose random index as pivot and partition the med array
pivot=rand()%mi;
i=low=0;
j=high=mi-1;
while(i<j) {
while(i<high && med[i]<=med[pivot]) i++;
while(med[j]>med[pivot]) j--;
if(i<j) {
temp2=med[i];
med[i]=med[j];
med[j]=temp2;
}
}
temp2=med[j];
med[j]=med[pivot];
med[pivot]=temp2;
//j is final position of pivot
//see if j is left/right or equal to the position of true median of median
// and recurse accordingly
low/=5;
high/=5;
if(j==(low+high)/2) return med[j];
else if(j<(low+high)/2) return getpivot(med,j+1,high);
else return getpivot(med,low,j-1);
}