0

让我困惑的作业练习：

我们有一个n随机顺序的整数数组，练习要求我们使用下面指定的方法对它们进行排序。

首先，我们按照两个规则将整数放在行中：

  1. 仅当 a < b 时，我们才将整数 a 放在整数 b 之上
  2. 否则我们将整数 a 放在新行中

这两条规则用于对数组进行排序。当我们完成应用规则时，我们选择较小的可见整数，一次一个，直到它们被排序。

该练习需要使用 3 个数组：

  1. data[1...n]其中包含要排序的数字
  2. column[1...n,1...]
  3. number[1..n]表示每列的整数总数

例如，如果

data = [3,2,12,8]

那么column将是：

column[1,1] = 3
column[2,1] = 2
column[1,2] = 12
column[2,2] = 8

并且number会是[2,2]

我正在尝试制作一个循环（请记住，英语中的伪代码可能与我用自然语言学习的伪代码不同）

for counter=1 to n 
    number[counter]:=0;
end for

for counter=1 to n
    a := 1;
    b := 1;

    if data[counter] < column[a,number[b]] or number[b]=0 then
        number[b] := number[b] + 1;
        column[a,number[b]] := data[counter];
    else 
        a:=a+1;
        b:=b+1;
    end if
end for

但是这段代码有很多错误。有人可以尝试解释我的逻辑哪里错了吗？

4

1 回答 1

0

由于您不知道rows最终会使用多少，因此您需要使用可增长的数据结构来表示您的rows，因此请使用列表。其次，由于rows正在堆叠数字，因此每一行都应该是一个堆栈。喜欢

List<Stack<Integer>> rows = new ArrayList<Stack<Integer>>();

那么你的算法最终将是 O(n^2)。您将遍历输入并将它们添加到行中

for(int i: input){
   boolean done = false;
   for(int x=0; x < rows.size() && ! done; i++)
     if(row.peep() > i){
       row.add(i);
       done = true;
     }
   if(!done)
     row.add(i);
}

完成填充行后，下一步是读回整数。你应该可以从这里拿走它。

于 2013-01-15T23:13:05.663 回答