java 按排序顺序将元素插入数组

Inserting an element into an array in sorted order

提问by Arun Prakash

I'm trying to add an element into an array in sorted order.

我正在尝试按排序顺序将元素添加到数组中。

This is my code :

这是我的代码：

public class SortedInsertion {

    public static void main(String[] args) {

        int[] arr=new int[6];
        arr[0]=5;
        arr[1]=6;
        arr[2]=9;
        arr[3]=11;
        System.out.println(Arrays.toString(arr));
        insert(7,arr);


    }

    public static void insert(int val,int[] arr){
        int i;
        for(i=0;i<arr.length-1;i++){

            if(arr[i]>val)
                break;
        }
        for(int k=i;k<arr.length-1;k++){
            arr[k+1]=arr[k];
            arr[i]=val;
        }
        System.out.println(Arrays.toString(arr));


    }

}

I'm getting the output as: [5, 6, 9, 11, 0, 0]

我得到的输出为：[5, 6, 9, 11, 0, 0]

[5, 6, 7, 9, 9, 9]

[5, 6, 7, 9, 9, 9]

But the right out put is

但正确的输出是

5,6,9,11,0,0

5,6,9,11,0,0

5,6,7,9,11,0

5,6,7,9,11,0

采纳答案by arin1405

Change the insertmethod like this:

insert像这样改变方法：

    public static void insert(int val,int[] arr){
      int i;
      for(i=0;i<arr.length-1;i++){
        if(arr[i]>val)
          break;
      }
      for(int k=arr.length-2; k>=i; k--){
        arr[k+1]=arr[k];            
      }
      arr[i]=val;
      System.out.println(Arrays.toString(arr));

    }

回答by Ruchira Gayan Ranaweera

There is an issues in your forloop

你的for循环有问题

for(i=0;i<arr.length-1;i++){}

It should iterate up to i<arr.length

它应该迭代到 i<arr.length

for(i=0;i<arr.length;i++){}

回答by SimY4

Here

这里

arr[k+1]=arr[k];

You're overriding every next array element with a previous value. You should probably reverse your loop and move from the end of the array, shifting all elements forward until you find the right spot, i.e.:

您正在使用先前的值覆盖每个下一个数组元素。您可能应该反转循环并从数组的末尾移动，将所有元素向前移动，直到找到正确的位置，即：

public static void insert(int val, int[] arr) {
    for(int i = arr.length - 1; i > 0; i--) {
        if (arr[i] == 0) continue; // skip last elements to avoid array index out of bound
        arr[i + 1] = arr[i];       // shift elements forward
        if (arr[i] <= val) {       // if we found the right spot
            arr[i] = val;          // place the new element and
            break;                 // break out the loop
        }
    }
    System.out.println(Arrays.toString(arr));
}

回答by Jay Shah

public class InsertInSortedArray {
        public static void main(String[] args) {
            int arr[] = {5, 6, 9, 11};
            Arrays.sort(arr);
            int k = 7;
            int index = findIndexToBeInserted(arr, k, 0, arr.length - 1);
            ArrayList<Integer> al = new ArrayList<>();
            for (int i : arr)
                al.add(i);

            al.add(index, k);
            for (int i : al)
                System.out.println(i);
        }

    private static int findIndexToBeInserted(int[] arr, int k, int start, int end) {
            if (k == 0)
                return 0;

            int mid = (start + end) / 2;

            if (k > arr[mid] && k < arr[mid + 1])
                return mid + 1;

            if (arr[mid] < k)
                return findIndexToBeInserted(arr, k, mid + 1, end);

            return findIndexToBeInserted(arr, k, start, mid - 1);
        }
    }

回答by Sergey Nemchinov

To be honest, the array in question is not really sorted like this: [0, 0, 5, 6, 9, 11].
It is a "zero tailed" array: [5, 6, 9, 11, 0, 0].
So to insert a value into that array it needs to know how many elements occupied are. In case when you provide this value into a method it would have O(log n) complexity. Otherwise, it needs to implement counting inside the inserting method.

说实话，有问题的阵列是不是真的排序是这样的：[0, 0, 5, 6, 9, 11]。
它是一个“零尾”数组：[5, 6, 9, 11, 0, 0]。
因此，要将值插入到该数组中，它需要知道所占用的元素数量。如果您将此值提供给方法，它将具有 O(log n) 复杂度。否则需要在插入方法内部实现计数。

/**
* @throws ArrayIndexOutOfBoundsException when the array is full and the value to be inserted is greater than the last element
*/
private static void insertToZeroTailedArray(int val, int[] arr) {
    // an O(n) operation to count occupied elements
    int elementsCount = 0;
    for (int i = arr.length - 1; i >= 0; i--) {
        if (arr[i] != 0) {
            elementsCount = i + 1;
            break;
        }
    }

    // binarySearch returns a negative position to insert if the value was not found
    int index = Arrays.binarySearch(arr, 0, elementsCount, val);
    if (index != 0) {
        int pos = index < 0
                ? -index - 1 // val not found, it is need to be inserted at (-index)-1 position
                : index;     // val found but we are going to insert it again

        // shift the array to right and drop last element because of the array bounds
        System.arraycopy(arr, pos, arr, pos + 1, arr.length - pos - 1);
        arr[pos] = val;
    } else {
        // the case when value is found at 0 position
        System.arraycopy(arr, 0, arr, 1, arr.length - 1);
        arr[0] = val;
    }
}

An alternative way to do what you need with O(log n) complexity for a really sorted array:

对于真正排序的数组，使用 O(log n) 复杂度执行所需操作的另一种方法：

private static void insertToReallySortedArray(int val, int[] arr) {
    int index = Arrays.binarySearch(arr, val);
    if (index != 0) {
        int pos = index < 0 ? -index - 1 : index;
        System.arraycopy(arr, pos, arr, pos + 1, arr.length - pos - 1);
        arr[pos] = val;
    } else {
        System.arraycopy(arr, 0, arr, 1, arr.length - 1);
        arr[0] = val;
    }
}

Based on this great answer.

基于这个很好的答案。

回答by Kaplan

completely unclear how an insert function should work without knowing the number of fields already occupied?

在不知道已经占用的字段数的情况下，完全不清楚插入函数应该如何工作？

public static void insert( int n, int occupied, int[] array ) {
  if( n >= array[occupied - 1] )
    array[occupied] = n;
  else
    for( int i = 0; i < array.length; i++ ) {
      int n1 = array[i];
      int n2 = array[i + 1];
      if( n1 > n || n1 < n && n2 >= n ) {
        if( n1 > n ) i--;
        System.arraycopy( array, i + 1, array, i + 2, occupied - i - 1 );
        array[i + 1] = n;
        break;
      }
    }
}

called from Your example above:

从上面的示例中调用：

…
arr[3]=11;
int occupied = 4;
insert( 7, occupied, arr );  // [5, 6, 7, 9, 11, 0]

unchecked bust with ArrayIndexOutOfBoundsExceptionif occupied >= array.length

未经检查的胸围ArrayIndexOutOfBoundsException如果occupied >= array.length

回答by Suhas

Another way of solving is by using List and collections.sort method.

另一种解决方法是使用 List 和 collections.sort 方法。

List<Integer> list = new ArrayList<Integer>(); 
  for (int i = 0; i < arr.length; i++) { 
  list.add(arr[i]); 
  } 
  list.add(val);

  Collections.sort(list);

 int[] result = list.stream().mapToInt(Integer::intValue).toArray();
 System.out.println(Arrays.toString(result));

Hope this solutions helps.

希望这个解决方案有帮助。

回答by Rakesh Chaudhari

Java Code,

Java代码，

public static void insertElementInSortedArr(int a[], int val) {

        int n[] = new int[a.length + 1];
        int j = 0;
        boolean isAdded = false;
        for (int i = 0; i < a.length; i++) {
            if (a[i] < val) {
                n[j] = a[i];
                j++;
            } else {
                if (!isAdded) {
                    n[j] = val;
                    j = j + 1;
                    isAdded = true;
                }
                n[j] = a[i];
                j = j + 1;
            }
        }
    }