我正在尝试使用快速排序对文件中存在的 100k 元素进行排序。只有当我使用第一个元素作为枢轴时，我的算法才有效。如何使枢轴元素对程序通用？选择枢轴元素的最佳方法是什么使用快速排序？枢轴元素是否依赖于数据，或者我们是否实时使用任何特定算法？
void quicksort(int *temp,int p,int r)
{
if(r > p + 1)
{
int piv = temp[p];
int left = p + 1;
int right = r;
while(left < right)
{
if(temp[left] <= piv)
left++;
else
swap(&temp[left], &temp[--right]);
}
swap(&temp[--left], &temp[p]);
quicksort(temp, p, left);
quicksort(temp, right, r);
}
}
最佳答案
对枢轴选择的限制是它需要相当快。常见的方法是选择第一个元素、选择中间元素或选择随机元素。
使用随机元素可能是最好的，因为即使对于已经排序的列表，它仍然倾向于快速排序(使用第一个元素在排序列表上的表现非常差，因为所有以下元素都会落在一侧枢轴)。
使用中间元素也相当安全，除非您的列表采用某种奇怪的非标准顺序，例如通过连接两个按相反顺序排序的列表会发现。
我建议随机选择。
My algorithm works only if I use first element as pivot
当你这么说时，你的意思是如果你的主元不是第一个元素，它会产生一个错误排序的列表？能说得更详细一点吗？
关于c - 如何使枢轴元素在快速排序中通用？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12325959/