c - 有什么不好的代码吗？ (C 上的快速排序时间复杂度)

Question

void QuickSort(int* x, int first, int last) {
    if (first >= last)
        ;
    else {
        int pivotindex = Partition(x, first, last);

        QuickSort(x, first, pivotindex - 1);
        QuickSort(x, pivotindex + 1, last); 
    }
}

int Partition(int* x, int first, int last) {
    int isbig = first + 1, issmall = last, tmp;

    while (1) {
        while (x[isbig++] < x[first] && isbig != last + 1);     // 

        while (x[issmall--] > x[first] && issmall != first);    // 

        if (isbig < issmall) {  //          tmp = x[issmall];
            x[issmall] = x[isbig];
            x[isbig] = tmp;
        }
        else {  //          tmp = x[first];
            x[first] = x[issmall]; 
            x[issmall] = tmp;

            break;  // 
        }
    }

    return issmall; //
}

我的这段代码有问题。我自己编码。它正在发挥作用。但是比我做的归并排序算法要慢一些。我找不到问题所在。(我知道合并排序和快速排序的时间复杂度在未排序的数据上是相等的，但在 10,000 个数据排序上是相同的: time comparison ignore korean )

它比合并排序大 10 倍。我认为这意味着代码很糟糕。但我找不到它在哪里。代码中是否有任何错误部分导致时间复杂度变大？

Answer 1

在最坏的情况下，快速排序的时间复杂度为O(n^2)，正如您在此处看到的那样。发生这种情况是因为您使用数组的第一个元素作为主元并对排序后的数据进行排序，因此数组被分为一个元素和 n-1 个元素。

为了比较，归并排序始终是O(n log n)。

您可以使用 x[(first + last)/2] 作为基准，而不是使用 x[first]。

参见:https://en.wikipedia.org/wiki/Quicksort#Choice_of_pivot