1

私はかなり新しいプログラマーであり、空の配列で開始するメソッドを作成し、その配列に昇順で値を追加するためにそれを呼び出すことができるようにしたいと考えています。

例えば：

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;
                }
            }
        }
    }
}
4

4 に答える 4

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 に答える