Inserting into array in order

问题:

In simple terms, part of the project I'm working on has me taking an array that is descending in order and adding an element so that it the array remains in order. Initially I thought it would be simple just to add the element into the array and then sort after implementing Comparable, but then found out that sorting algorithms of any kind are prohibited; Collections as well. Kind of out of ideas on how to proceed from here, any hints?

EX:

int[] x = [ 7, 6, 6, 5, 3, 2, 1 ] 

add 4

[ 7, 6, 6, 5, 4, 3, 2, 1 ]

Clarification to say that I am not completely out of ideas, just efficient ones. What I am able to reason so far:

int[] bigger = new int[x.length];
int add = 4;
for (int i = 0; i < bigger.length; i++){
     if ( add > x[i] && add < x[i+1]){
         bigger[i] = x[i];
         bigger[i+1] = add;
     else{
         bigger[i] = x[i];
     }
}

I know it will throw an IndexOutOfBounds error for x, but I feel there must be a simpler method than this, right?

回答1:

Actually, only one for-loop can implement your function.

    int[] x = {7, 6, 6, 5, 3, 2, 1 };
    //Declare an int array with length = x.length+1;
    int[] bigger = new int[x.length+1];
    int add = 4;
    /** Define a variable to indicate that if a property location is found.*/
    boolean found = false;
    /** Define a variable to store an index for insert*/
    int indexToInsert = 0;
    for (int i = 0; i < x.length; i++){
         if ( !found && add >= x[i]){
             found = true;
             indexToInsert = i;
             bigger[indexToInsert] = add;
             i--;
         }
         else{
             if(found)
             {
                 bigger[i+1] = x[i]; 
             }else
             {
                 bigger[i] = x[i];
             }

         }
    }

    /*
     * If a property index is not found. Then put the value at last. 
     */
    if(!found)
    {
        indexToInsert = x.length;//
        bigger[indexToInsert] = add;
    }

Some example is run as follows:

Initail array is [7, 6, 6, 5, 3, 2, 1]

add = 4

 [7, 6, 6, 5, 4, 3, 2, 1]

add = -1

 [7, 6, 6, 5, 3, 2, 1, -1]

add = 100

 [100, 7, 6, 6, 5, 3, 2, 1]

回答2:

Once you find the right place i.e. if(value < list[i]){ is true then move all available elements to right. You are moving only one by using list[i+1]= list[i];

   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++;

回答3:

int add = 4;

int[] newArray = new int[oldArray.length + 1];

int oldPos = 0;
int newPos = 1;
while (oldPos < oldArray.length) {
    if (add > oldArray[oldPos]) {
        break;
    }
    newArray[newPos] = oldArray[oldPos];
    oldPos++;
    newPos++;
}

newArray[newPos] = add;
newPos++;

while (oldPos < oldArray.length) {
    newArray[newPos] = oldArray[oldPos];
    oldPos++;
    newPos++;
}

Or one could use System.arraycopy to finish out the copy operation -- slower for a small array but faster for a large one.