c# - C# 中的快速排序错误复杂度

Question

我正在对排序算法进行一些分析，但遇到了快速排序的问题。在网上找了一些图表，看到我的图表和其他的图表有很大的不同，我想知道为什么。

这是我的代码：

static int Particao(int[] vet, int min, int max, int modo)
{
    int i = min;
    int j = max;            
    int pivot;

    if (modo == 0)
        pivot = vet[(min + max) / 2];
    else
        pivot = vet[min];            
    while (i <= j)
    {
        while (vet[i] < pivot)
            i++;
        while (vet[j] > pivot)
            j--;
        if (i <= j)
        {
            int aux = vet[i];
            vet[i] = vet[j];
            vet[j] = aux;
            i++;
            j--;
        }
    };

    return i;
}

static void QuickSort(int[] vet, int ini, int fim)
{
    int pivo = Particao(vet, ini, fim, 0);

    if (ini < pivo - 1)
        QuickSort(vet, ini, pivo - 1);
    if (pivo < fim)
        QuickSort(vet, pivo, fim);            

}

我的图表（时间以毫秒为单位乘以 1000）：

谢谢 =)

标签： c#algorithmsortingtime-complexityquicksort

Answer 1

由于测量值不同，您的图表与其他图表不同。其他图表有更多的数据点和许多平均测量值，以防止错误。

您的图表只有 6 个数据点，每个数据点有 1 个测量值，因此很难从中得出任何结论。

也许您可以测量掉期或比较的数量并从中推断出图表？