0

我有以下算法来订购一个有 10 个数字的 .txt 文件

for (int i=0;i<array.length;i++)
{
    for(int j=i;j<array.length;j++)
    {
        if (array[i]<array[j])
        {
            temp=array[i];
            array[i]=array[j];
            array[j]=temp;
        }
    }
}

它会按顺序写入一个包含所有数字的新 .txt 文件。但是用笔和纸说它不应该工作。如下：

7 10 4 3 5 8 1 3

该算法应该这样做：

10 7 4 3 5 8 1 3
10 8 4 3 5 7 1 3
10 8 5 3 4 7 1 3
10 8 5 4 3 7 1 3
10 8 5 4 7 3 1 3
10 8 5 4 7 3 3 1

显然，最后一行没有按顺序排列，那么为什么代码做对了呢？或者......当我用笔和纸做的时候我错在哪里？

4

3 回答 3

5

为什么它不应该工作？这是一个非常基本的排序算法（称为选择排序）。你的钢笔和铅笔的问题是你忘记了外层for。继续对每个项目进行排序。这就是它O(n^2)复杂的原因。

于 2013-07-24T16:42:20.717 回答
0

为什么它不起作用？对于每个位置 i，内部循环有效地将列表其余部分的最大成员移动到该位置（使其成为选择排序）。

我认为您的论文演练在第三步出错了；我得到：

7 10 4 3 5 8 1 3 <- original list
^i
10 7 4 3 5 8 1 3
   ^i
10 8 4 3 5 7 1 3
     ^i
10 8 7 3 4 5 1 3
       ^i
10 8 7 5 3 4 1 3
...
于 2013-07-24T16:44:29.790 回答
0

我会重新检查你的第三个结果：

10 8 5 3 4 7 1 3

在将“4”换出后，您最终以“5”作为您的第三个数字，但这还没有完成。如果您继续迭代“j”循环，它将继续测试其余数字。如果我们要正确运行该循环，它看起来更像这样：

Starting with 10 8 4 3 5 7 1 3 where i points to the third digit '4':
if (4 < 4) false  // This is an unecessary step FYI, should start the loop with j=i+1
if (4 < 3) false
if (4 < 5) true, swap 4 with 5 = 10 8 5 3 4 7 1 3
  // This is where you seem to have stopped your loop and jumped directly to the next i,
  // However, there is no break and the j loop should continue on using the new third
  // digit '5'...
if (5 < 7) true, swap 5 with 7 = 10 8 7 3 4 5 1 3
if (7 < 1) false
if (7 < 3) false

您最终得到结果 10 8 7 3 4 5 1 3 作为您的第三次迭代。

于 2013-07-24T16:53:41.533 回答