快速排序C语言中的中位数枢轴元素

Question

我正在尝试使用中位数枢轴元素实现快速排序算法... 如果没有数字出现两次，我的代码可以正常工作，但这绝不是解决方案。 如果我选择分区的第一个元素作为枢轴，无论值是否出现两次或更多次，代码都能完美运行...

以下是我的代码：

void quickSort(int a[ ], int from, int to)
{ // sort partition from ... to of array a
    int i, pivot, new_val;
    if (from < to) // at least 2 elements in partition
    {
        //pivot = from; --> old version, first element is pivot
        pivot = median(a, from, to);
        for (i = from; i <= to; i++)
        {
            new_val = a[i];
            if (new_val < a[pivot])
            { // shift values to the right
                a[i] = a[pivot+1];
                a[pivot+1] = a[pivot];
                a[pivot] = new_val;
                pivot++;
            } // else a[i] stays put
        }
        quickSort(a, from, pivot-1); // left partition
        quickSort(a, pivot+1, to); // right partition
    } // else (from >= to) only 0 or 1 elements
} // end quicksort

int median(int a[], int from, int to)
{
    int med = (from + to) / 2;
    if((a[from] < a[med] && a[med] <= a[to]) || (a[to] < a[med] && a[med] < a[from]))
        return med;
    else if((a[med] < a[from] && a[from] < a[to]) || (a[to] < a[from] && a[from] < a[med]))
        return from;
    else if((a[med] < a[to] && a[to] < a[from]) || (a[from] < a[to] && a[to] < a[med]))
        return to;
}

我做错了什么吗？

提前感谢！

（请注意，保留了HTML标签）

- RoodRallec

---

那个 for (i = from + 1; 部分在使用起始位置做为 pivot 时是完全有意义的，但使用中位数时就不那么有意义了。 - H H

是的，没错，我已经改过了，但是好像什么也没改变 :( - RoodRallec

Answer 1

当一些元素相等时，您的中位数函数会失败。 如果输入是3、3和3，则函数中的任何条件都不会评估为true。

在这种情况下，函数找不到任何返回语句，行为未定义。 尝试在条件中使用“<=”而不是“<”。

此外，您正在使用“pivot + 1”而没有确保“pivot”不是最后一个元素。 如果中位数是数组的最后一个元素，程序将崩溃。

您确定它适用于正常输入吗？因为我尝试过，该函数无法正确排序数组。 您可以在此处找到有关分区例程的良好解释。

- merlyn