插入排序的比较时间复杂度

Question

我已经在C(Visual Studio)和Java(Eclipse)中实现了插入排序，以分析完成所需的时间，并比较两种语言之间的差异。

我试图找出算法补全所需的最坏情况时间。(将递减数组转换为递增数组)。

我用10,000、50,000和100,000个条目的样本运行我的代码，下面是观察结果:

In C:
10000: 0.172 seconds
50000: 3.874 seconds
100000: 15.384 seconds
whereas in Java
10000: 0.048 seconds
50000: 0.385 seconds
100000: 1.924 seconds

我的代码是正常的插入排序代码。没什么新鲜的。测量的时间仅用于插入排序代码，i/o操作与此无关。例句:

Input
Timer starts here
Insertion Sort
Timer ends
Summary(Time required and all)

我相信C比Java快，但我无法证明这个结果。

编辑:这是C代码

void InsertionSort(int a[]) {
    int i;
    clock_t st, end;
    st = clock();
    for (i = 1; i < MAX; i++)   {
        int temp = a[i];
        int pos = i - 1;
        while(a[pos] > temp)    {
            a[pos + 1] = a[pos];
            pos--;
        }
        a[pos + 1] = temp;
    }
    end = clock();
    printf("nSorting Completed. Time taken:%f", (double)(end - st) / CLOCKS_PER_SEC);
}

和Java代码:

public void Sort(int a[], int size) {
        int i;
        for (i = 1; i < size; i++)  {
            int temp = a[i];
            int pos = i - 1;
            while(pos >= 0 && a[pos] > temp)    {
                a[pos + 1] = a[pos];
                pos--;
            }
            a[pos + 1] = temp;
        }
}

Answer 1

我无法让jconsole打印时间，所以我在Linux上使用了最原始的方法来比较时间(我使用了您的插入排序实现)。

C (gcc is alize to gcc -Wall -Wextra -Wunreachable-code -Waggregate-return -Wshadow):

$ gcc -O3 insertion_sort.c 
$ date; ./a.out; date
Tue Jun 11 20:16:24 MYT 2013
Tue Jun 11 20:16:36 MYT 2013

Java:

$ javac Main.java
$ date; java Main; date
Tue Jun 11 20:19:11 MYT 2013
Tue Jun 11 20:19:32 MYT 2013

很明显C优于Java，我使用了一个大小为150000的数组，并进行了反向排序。我提供了我的代码链接:

C

Java

我的建议是设置一个运行Linux操作系统的虚拟机并自己尝试(学习一些Linux非常有用，更不用说C编程了)。