java - 如何为我的数组创建 insertInOrder 方法

Question

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

例如:

insertInOrder(5);

insertInOrder(3);

insertInOrder(7);

insertInOrder(9);

insertInOrder(12);

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

0:3

1:5

2:7

3:9

4:12

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

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

例如:

insertInOrder(1);

insertInOrder(4);

insertInOrder(9);

insertInOrder(17);

insertInOrder(26);

可以工作，但此代码不会:

insertInOrder(2);

insertInOrder(4);

insertInOrder(1);

insertInOrder(3);

insertInOrder(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;
                }
            }
        }
    }
}

Answer 1

我相信如果您想要具有良好的插入复杂性并按排序顺序存储元素，您需要更复杂的数据结构。一个self-balancing binary search tree就像 RB tree会工作，你也可以使用 skip list作为一个更简单的选择。

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