0

我正在编写一个实现插入排序算法对数组进行排序的程序：

 public void insertionSort()
{
    int in, out;

    for (out = 1; out < nElems; out++)     // out is dividing line
    {
        copies++;                       
        long temp = a[out];            // remove marked item
        in = out;                      // start shifts at out
        while (in > 0 && a[in - 1] >= temp) // until one is smaller,
        {
            a[in] = a[in - 1];            // shift item to right
            --in;                       // go left one position
            ++comparissons;             
        }
        a[in] = temp;                  // insert marked item
    }  // end for
}  // end insertionSort(

我还实现了计算在算法过程中进行了多少比较的计数器。在我的while循环中：

 while (in > 0 && a[in - 1] >= temp) // until one is smaller,
    {
        a[in] = a[in - 1];            // shift item to right
        --in;                       // go left one position
        ++comparissons;             
    }

进行了两次比较，这意味着对于这两次比较，“比较”变量仅增加一（即使实际上进行了两次比较）。

我的问题是：如何通过两个比较将这个 while 循环分解为两部分，以便每次实际进行比较时增加“比较”，同时保留相同的功能。

谢谢！

仲量联行

4

2 回答 2

1

您是指while条件下的比较吗？如果是，只需分别检查这些条件

while (in > 0) // until one is smaller,
{
    ++comparissons; 
    if (a[in - 1] >= temp)   ++comparissons;
    else                     break;

    a[in] = a[in - 1];            // shift item to right
    --in;                       // go left one position           
}
于 2013-10-02T22:19:03.780 回答
1

将比较移动到 while 循环内的 if 中。

while (in > 0) {
    // Move the comparison increment here.
    if (a[in -1] >= temp) {
       // The rest of the original while code here.   
    } else {
       break;
    }
}

或者你可以做一个这样的hack，并将比较增量移动到条件本身。

while (in > 0 && ((a[in-1] >= temp) && (++comparisons > -1))) {
}
于 2013-10-02T22:16:41.273 回答