0

我正在为我的编程课做额外的学分作业。我们正在做 OOP，这个例子是获取一个数组并对其进行排序。所有的排序代码都将进入 add 方法。我已经有一些代码，并且它可以工作。正如标题中所说，我必须使用我独特的代码创建自己的算法。如何将列表中的所有整数从小到大排序？（整数是使用 add 方法添加的值。）这是讲师给我的说明：

• 沿着阵列向下走，直到找到新元素应该去的地方。由于列表已经排序，您可以继续查看元素，直到找到至少与要插入的元素一样大的元素。

• 下移将在新元素之后的每个元素，即从您停止的元素到最后的所有元素。这将创建一个插槽，您可以在其中放置新元素。请注意移动它们的顺序，否则您将覆盖您的数据！

现在您可以在您最初停止的位置插入新元素。所有这些都将进入您的 add 方法。

程序的两个类：

   private int[] list;
   private int numElements = 0;



   //-------------------------------------------------------------
   // Constructor -- creates an integer list of a given size.
   //-------------------------------------------------------------
   public IntList(int size)
   {
      list = new int[size];
   }
   //------------------------------------------------------------
   // Adds an integer to the list. If the list is full,
   // prints a message and does nothing.
   //------------------------------------------------------------

   public void add(int value)
   {
      if (numElements == list.length){
      System.out.println("Can't add, list is full");
      }
      else
      { 
        list[numElements] = value;
        for(int i = 0; i < numElements; i++){
            //May be I should use a nested loop?
            //for(k = 0; k <)
             if(value < list[i]){
                 list[i+1]= list[i];
                 list[i]=value;
             }
       }
        numElements++;

            }


      }



   //-------------------------------------------------------------
   // Returns a string containing the elements of the list with their
   // indices.
   //-------------------------------------------------------------
   public String toString()
   {
      String returnString = "";
      for (int i=0; i<numElements; i++)
         returnString += i + ": " + list[i] + "\n";
      return returnString;
   }
}

另一类：

public class IntListThing {


public static void main(String[] args){

          IntList myList = new IntList(10);
          myList.add(84);
          myList.add(27);
          myList.add(250);
          myList.add(18);
          myList.add(94);
          myList.add(8);
          myList.add(87);
          System.out.println(myList);
       }
    }
4

5 回答 5

4

一旦找到正确的位置，即为if(value < list[i]){真，然后将所有可用元素向右移动。您只使用 移动一个list[i+1]= list[i];。

即使用一个小循环：

  for(int j= numElements-1; j>=i; j--){
      list[j+1]= list[j];
  }
  list[i] = value;

请注意：这是概念。请调整指标和条件。

编辑：我错过了提到你需要在插入元素后立即中断。我也纠正了条件。这是更新的else块代码。

        list[numElements] = value;
        for(int i = 0; i < numElements; i++){
            //May be I should use a nested loop?
            //for(k = 0; k <)
             if(value < list[i]){
                 for(int j= numElements-1; j>=i; j--){
                      list[j+1]= list[j];
                  }
                  list[i] = value;
                  break;
            }
        }
        numElements++;
于 2012-11-09T20:46:27.097 回答
2

如果您真的想对您的教授产生影响，请对插入点进行二进制搜索。找到它后，退出该循环并进入另一个循环，将插入点之外的所有内容复制到右侧一个位置。

编辑

正如@Jan Dvorak 在下面尖锐指出的那样，即使是二进制搜索也是浪费 CPU 时间和编程工作:)

于 2012-11-09T20:56:05.457 回答
1

由于这是一项家庭作业，因此许多人不愿意直接给您代码。

您在评论中使用嵌套循环暗示的内容是必要的。您使用此循环的目标是将每个元素“推回”list一个位置。一些考虑：

1）一定要检查你的数组的边界。如果你的数组是“满的”，那么把东西推到极限会导致ArrayOutOfBoundsException.

2) 在循环中移动时注意不要覆盖任何值。我可以建议从后面开始并向前推进吗？

于 2012-11-09T20:56:21.773 回答
0

试试这个

class IntListThing  {
private int[] list;
private int numElements;

public IntListThing  ( int initial_capacity ) {
    list = new int[initial_capacity>0?initial_capacity:1];
    numElements = 0;
}

public void add(int value)  {
      if (numElements == list.length) list = Arrays.copyOf(list, list.length*2);
      int i = 0;
      for ( i = 0 ; i < numElements ; ++i ) 
          if ( value < list[i] ) break; 
      for ( int k = numElements ; k > i ; --k )
          list[k] = list[k-1];
      list[i] = value;
      ++numElements;
}

public String toString()  {
      String returnString = "";
      for (int i=0; i<numElements; i++)
         returnString += i + ": " + list[i] + "\n";
      return returnString;
   }


}

这样你也不必担心你的数组会变满，它会在需要时调整大小。

在 Arrays 类中，您可以找到各种其他有用的方法。你一定要检查一下。您有某人建议使用的 binarySearch，但这在这里非常不合适，因为在这种方法中，您已经具有复制数组的线性复杂性，所以在对数时间内进行搜索有什么意义。

我希望你能得到额外的荣誉。

如果您想进行更多练习，请尝试创建一个删除方法，该方法还可以在需要时调整数组大小以节省空间。如果您需要帮助，请在评论中告诉我。

于 2012-11-09T21:10:15.850 回答
0

经典的插入排序通过将一个元素向左交换直到它被排序，然后移动到下一个元素，只将被移动的元素写入它没有被覆盖的地方：

- input: array a
- for i from 1 to a.length-1: // the first element is already sorted!
  - temp = a[i];
  - j = i;
  - while (j>0 && a[j-1] < temp):
    - a[j] = a[j-1];
    - j = j-1;
  - endwhile
  - a[j] = temp;
- endfor
- output: a
于 2012-11-09T21:14:11.660 回答