1

我是一个相当新的程序员，想要创建一个以空数组开头的方法，并允许我调用它，以便按升序向该数组添加值。

例如：

插入顺序（5）；

插入顺序（3）；

插入顺序（7）；

插入顺序（9）；

插入顺序（12）；

应该返回一个包含值的数组：

0:3

1:5

2：7

3：9

4：12

任何关于如何在不使用诸如“Array.sort”之类的 java 预构建方法的情况下解决此问题的提示将不胜感激。谢谢！

下面是我对这段代码的尝试；但是，我所能实现的只是在数组末尾添加一个值，如果它是最大的数。

例如：

插入顺序（1）；

插入顺序（4）；

插入顺序（9）；

插入顺序（17）；

插入顺序（26）；

会工作，但这段代码不会：

插入顺序（2）；

插入顺序（4）；

插入顺序（1）；

插入顺序（3）；

插入顺序（19）；

代码：

public class InOrder 
{
int[] arry = new int[20];
int target = -1;
int elements = 0;

public static void main(String[] args) 
{
    InOrder i = new InOrder();
    i.insertInOrder(6);
    i.insertInOrder(7);
    i.insertInOrder(12);
    i.insertInOrder(17);
    i.insertInOrder(19);
    i.insertInOrder(28);


    for(int k = 0; k < 20; k++)
    {
        System.out.println(i.arry[k]);
    }
}

public void insertInOrder(int n) 
{

    if (elements == 0) 
    {
        arry[0] = n;
        elements++;
    }

    else 
    {
        for (int i = 0; i < elements; i++) 
        {
            if (n > arry[i]) 
            {
                target = i;
            }
        }

        if (target == -1) 
        {
            target = 0;
        }

        if (n > arry[target]) 
        {
            for (int x = target; x < elements; x++) 
            {
                if(x + 1 == elements)
                {
                    arry[x + 1] = n;
                    elements++;
                    break;
                }
            }
        }
    }
}
4

4 回答 4

1

我相信如果您想要具有良好的插入复杂性并按排序顺序存储元素，您需要一个更复杂的数据结构。像RB 树这样的自平衡二叉搜索树可以工作，您也可以使用跳过列表作为更简单的选项。

如果您不关心复杂性，只需在每个插入操作上对数组进行排序。

于 2013-09-13T12:32:54.187 回答
0

如果始终插入已排序，则可以使用高效的二分搜索，换句话说，如果数组始终保持排序状态。

import java.util.Arrays;

public class InOrder
{
  int[] array = new int[20];
  int target = -1;
  int elements = 0;

  public static void main(String[] args) 
  {
      InOrder i = new InOrder();
      i.insertInOrder(6);
      i.insertInOrder(17);
      i.insertInOrder(28);
      i.insertInOrder(19);
      i.insertInOrder(7);
      i.insertInOrder(12);

      for(int k = 0; k <i.elements; k++)
      {
          System.out.println(i.array[k]);
      }
  }

  public void insertInOrder(int n) 
  {
    if(elements==array.length) array=Arrays.copyOf(array, elements*2);
    int pos = Arrays.binarySearch(array, 0, elements, n);
    if(pos<0) pos=~pos;
    if(pos<elements) System.arraycopy(array, pos, array, pos+1, elements-pos);
    array[pos]=n;
    elements++;
  }
}
于 2013-09-13T12:40:20.927 回答
0

您想要做的是作为插入排序的一部分。

高层描述：

Let the current position point to the last element
While the element to insert is smaller than the element at the current position
  Move the element at the current position right one
  Decrease the current position
Insert the element at the current position

伪代码：

holePos ← length(A)
while holePos > 0 and valueToInsert < A[holePos - 1]
{ //value to insert doesn't belong where the hole currently is, so shift 
    A[holePos] ← A[holePos - 1] //shift the larger value up
    holePos ← holePos - 1       //move the hole position down
}
A[holePos] ← valueToInsert

转换为 Java 代码应该很容易。

但是，是的， Ivaylo 建议的 BST会更有效。

于 2013-09-13T12:41:02.737 回答
0

您可以使用此代码。可以改变参数类型。

public void insert(int x) {
    // loop through all elements
    for (int i = 0; i < size(); i++) {
        // if the element you are looking at is smaller than x, 
        // go to the next element
        if (get(i) < x) continue;
        // if the element equals x, return, because we don't add duplicates
        if (get(i) == x) return;
        // otherwise, we have found the location to add x
        add(i, x);
        return;
    }
    // we looked through all of the elements, and they were all
    // smaller than x, so we add ax to the end of the list
    add(x);
}
于 2013-09-13T12:32:53.417 回答