Java - 为什么我的冒泡排序比插入排序更快？

Question

我正在测量排序完成排序所需的步骤数，无论出于何种原因，冒泡排序似乎总是比插入排序快一点，从我读到的内容来看，它应该是相反的。

不会发布我的完整代码，但我相信问题可能出在我的计数位置。

冒泡排序:

public void sort()
{
    for (out = nElems-1 ; out >= 1 ; out--)
    {
        count = count+1;
        for (in = 0 ; in < out ; in++)
        {
            if ((a.get(in)) > (a.get(in+1)))
            {
                swap (in, in+1);
                count = count+2;
            }
        }
    }
}

插入排序:

void sort()
{
    Integer temp[] = new Integer[1];
    for (out = 1 ; out < nElems ; out++)
    {
        count = count+1;
        temp[0] = a.get(out);
        in = out;
        while (in > 0 && a.get(in-1) >= temp[0])
        {
            a.set(in, a.get(in-1));
            --in;
            count = count+2;
        }
        a.set(in, temp[0]);
    }
}

举个例子，我对 3 个文本文件进行了排序，其中填充了 2000 个随机整数，值范围为 1-2000，插入排序的平均值为 2,007,677 步，冒泡排序的平均值为 2,005,719 步。

Answer 1

所以，首先，您只是衡量任务，而不是整体表现。其次，您的插入排序具有不交换来移动值的优化，那么为什么您每次都将 2 添加到 count 中呢？您的 while 循环应该只向 count 添加 1，然后当您有 a.set(in,temp[0]) 时，您应该在 while 循环之外再次添加 1 >。 (旁注 - 为什么 temp 是一个数组而不仅仅是一个整数？)现在，如果您想衡量整体性能，则需要衡量比较和分配(最好在两个单独的变量中，因为某些设备/架构对于这些操作可能具有非常不同的性能)。

编辑:

澄清一下，比较是指使用小于 (<) 或大于 (>) 等运算符来比较数组中两个项目的值。赋值是指您更改数组中的值(在您的情况下，使用 a.set())。

这里有一些代码修改(我将 count 分成两个变量，代表您想要测量的实际内容，分配和比较 ):

冒泡排序:

public void sort()
{
    for (out = nElems-1 ; out >= 1 ; out--)
    {
        for (in = 0 ; in < out ; in++)
        {
            comparisons = comparisons+1;
            if ((a.get(in)) > (a.get(in+1)))
            {
                swap (in, in+1);
                assignments = assignments+2;
            }
        }
    }
}

插入排序:

void sort()
{
    int temp = 0;
    for (out = 1 ; out < nElems ; out++)
    {
        count = count+1;
        temp[0] = a.get(out);
        in = out;
        comparisons = comparisons + 1; //You're doing the comparison below at least once
        while (in > 0 && a.get(in-1) >= temp[0])
        {
            a.set(in, a.get(in-1));
            --in;
            assignments = assignments+1;
            comparisons = comparisons + 1; 
        }
        a.set(in, temp[0]);
        assignments = assignments+1;
    }
}

还有一件事需要考虑 - 您在哪里初始化变量 count？我在您的代码中没有看到它，实际上可能是您在不同范围内使用相同的变量，并且由于您没有将其重置为 0，所以无论您第二次执行哪种排序都会添加到从您的第一个数字开始。