2.1.31

2.1.31 #

解答 #

这里截取数据量比较大的时候的数据。

插入排序和选择排序显然都是平方级别的。

希尔排序猜测是线性的，实际上要比线性大一点（次平方级）。

代码 #

var n = 1000;

var insertion = new InsertionSort();
var selection = new SelectionSort();
var shell = new ShellSort();

double prevInsertion = 0;
double prevSelection = 0;
double prevShell = 0;

for (var i = 0; i < 10; i++)
{
    Console.WriteLine("N:" + n);
    var array = SortCompare.GetRandomArrayInt(n);
    var arrayBak = new int[n];
    array.CopyTo(arrayBak, 0);

    Console.WriteLine("\tInsertion Sort");
    var now = SortCompare.Time(insertion, array);
    Console.WriteLine("\t\tActual Time(ms):" + now);
    if (i != 0)
    {
        Console.WriteLine("\t\tEstimate Time(ms):" + prevInsertion * 4);
        Console.WriteLine("\t\tRatio:" + now / prevInsertion);
    }

    prevInsertion = now;

    arrayBak.CopyTo(array, 0);

    Console.WriteLine("\tSelection Sort");
    now = SortCompare.Time(selection, array);
    Console.WriteLine("\t\tActual Time(ms):" + now);
    if (i != 0)
    {
        Console.WriteLine("\t\tEstimate Time(ms):" + prevSelection * 4);
        Console.WriteLine("\t\tRatio:" + now / prevSelection);
    }

    prevSelection = now;

    arrayBak.CopyTo(array, 0);

    Console.WriteLine("\tShell Sort");
    now = SortCompare.Time(shell, array);
    Console.WriteLine("\t\tActual Time(ms):" + now);
    if (i != 0)
    {
        Console.WriteLine("\t\tEstimate Time(ms):" + prevShell * 2);
        Console.WriteLine("\t\tRatio:" + now / prevShell);
    }

    prevShell = now;

    n *= 2;
}

另请参阅 #

Sort 库