以排序方式在数组中插入整数的函数

Question

所以假设我从数组 [0,0,0,0] 开始。在这个数组中，我将恰好添加 4 个值。让我们说2,1,3,4。所以我的主要功能看起来像：

 public static void main(String[] args) {
        int[] arr = new int[4];
        insertSortedInArr(2,arr);
        insertSortedInArr(1,arr);
        insertSortedInArr(3,arr);
        insertSortedInArr(4,arr);
    }

我尝试了一种方法 insertSortedInArr() 的实现，该方法也是在网上找到的，但效果不佳。我试图找出它出了什么问题，但我无法找到错误。这是方法：

 public static void insertSortedInArr(int val,int[] arr){
        int i;
        for(i=0;i<arr.length-1;i++){
            if (arr[i] == 0){
                arr[i] = val;
                return;
            }
            if (val < arr[i])
                // value must be inserted in arr[i]
                break;
        }
        // move everything right
        for(int k=i; k<arr.length-1; k++){
                arr[k+1]=arr[k];
        }
        arr[i]=val;
    }

此方法的输出结果为：[1, 2, 2, 4]。如果您能找到问题所在或更好地实现此方法，我们将不胜感激。谢谢

Answer 1

问题出在“将所有内容都正确”部分。

您正在从左到右迭代，但这将覆盖下一个元素。

相反，从右到左迭代：

for (int k=arr.length-1; k > i; k--){
    arr[k]=arr[k - 1];
}

Answer 2

既然你已经知道了这些值，我想我们甚至不需要在这里循环。我们可以执行以下操作：

public static void insertSorted(int val, int arr[]) {
    if(arr[val - 1] == 0) { 
        arr[val-1] = val;
    }
}

或更好，只需将值以随机顺序插入数组，然后使用

Arrays.sort(arr);

希望对您有所帮助。

Answer 3

在检测应移动可用值的第一个空闲元素方面可以进行一些小的改进：

public static void insertSortedInArr(int val, int[] arr) {
    int i;
    for (i = 0; i < arr.length; i++) {
        if (arr[i] == 0) {
            break;
        } else if (val < arr[i]) {
            int j;
            for (j = i + 1; arr[j] != 0 && j < arr.length; j++); // find first 0
            for (int k = j; k > i; k--) { // shift elements right to the first free cell
                arr[k] = arr[k - 1];
            }
            break;
        }
    }
    arr[i] = val;
    System.out.println(Arrays.toString(arr));
}

测试：

int[] arr = new int[4];
insertSortedInArr(4,arr);
insertSortedInArr(2,arr);
insertSortedInArr(1,arr);
insertSortedInArr(3,arr);

输出：

[4, 0, 0, 0]
[2, 4, 0, 0]
[1, 2, 4, 0]
[1, 2, 3, 4]

以排序方式在数组中插入整数的函数

Function to insert integers in an array in a sorted way

java

arrays

sorting

integer