0

我正在尝试使用快速排序对文件中存在的 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);
    }
}
4

1 回答 1

1

对枢轴选择的限制是它需要相当快。常见的方法是选择第一个元素、选择中间元素或选择随机元素。

使用随机元素可能是最好的，因为即使对于已经排序的列表，它仍然倾向于快速排序（使用第一个元素在排序列表上的表现会很差，因为以下所有元素都将落在枢轴的一侧）。

使用中间元素也是相当安全的，除非你的列表是一些奇怪的非标准顺序，比如你可以通过连接两个以相反顺序排序的列表来找到它。

我建议随机选择。

我的算法只有在我使用第一个元素作为枢轴时才有效

当您这么说时，您的意思是如果您的枢轴不是第一个元素，它会产生一个错误排序的列表吗？你能说得更详细些吗？

于 2012-09-07T22:09:08.123 回答