c - QuickSort C 中位数枢轴元素

Question

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

这是我的代码:

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;
}

我做错了什么？？

提前致谢!

Answer 1

当某些元素彼此相等时，您的中值函数将失效。
如果输入是 3、3 和 3，则函数中的条件都不计算为真。

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

此外，您正在使用 pivot + 1不确定 pivot不是最后一个元素。
如果中位数是数组的最后一个元素，程序就会崩溃。

你确定它适用于正常输入吗，因为我试过了，但这个函数没有正确地对数组进行排序。
您可以在分区例程中找到很好的解释 here .