java顺序数组插入元素

本文主要阐明已知顺序数组，在数组中插入一个数据元素，使其仍然保持有序。

关键是寻找num在原数组中插入的位置；

当num在原数组中是最大的情况，num应该插入到原数组的末尾。

否则，应该遍历原数组，通过比较原数组元素和num，找到插入位置，进行右移，最后在指定位置上插入num元素。

public class Two {

    public int[] SortArray(int[] arr,int num) {

        int index = 0;

        int[] arr_copy = new int[arr.length+1];

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

            arr_copy[i] = arr[i];

        }

        // 最后一个元素

        if(arr_copy[arr.length-1] <= num) {

            arr_copy[arr_copy.length-1] = num;

            return arr_copy;

        }

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

            if(arr_copy[i] > num) {

                index = i;

                break;

            }

        }

        // 将index之后的数据右移，空出index索引指向的空间。

        // i > index，不能是i >= index;

        // 当index = 0 时，若i >= index，则最后一次循环i = 0，则

        // arr_copy[i] = arr_copy[i-1];  数组越界报错!!!

        for(int i = arr_copy.length-1;i > index;i--) {

            // index之后的数据向右移动

            arr_copy[i] = arr_copy[i-1];

        }

        arr_copy[index] = num;

        return arr_copy;

    }

    public static void main(String[] args) {

        int[] arr = {10,12,45,90};

        // 加入23后依然是升序

        System.out.println("请输入数据:");

        Scanner scanner = new Scanner(System.in);

        int num = scanner.nextInt();

        Two obTwo = new Two();

        arr = obTwo.SortArray(arr, num);

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

            System.out.print(arr[i] + " ");

        }

    }

}

韩老师思路：

首先定位，用index表示要插入的位置，遍历原来的数组，如果原来数组元素大于或等于num，index指向该元素的索引。否则，index的值不发生变化，即num是最大值，插入原来数组的末尾。

注意，这里的插入操作有些技巧。

用 i 指针指向新数组，j 指针指向旧数组。当 i 不等于index时，即 i 不是要插入的位置时，arr_copy[ i ] = arr[ i ] ，i++，j++；

当 i 等于index时，即 i 指向了要插入的位置时，arr_copy[ i ] = num ，i++，j不做自增操作。

具体代码如下：

for(int i = 0,j = 0;i<arr_copy.length;i++) {

    // 当i!=index时，即不是要插入的位置，

    if(i != index) {

        arr_copy[i] = arr[j];

        j++;

    }else {

        arr_copy[i] = num;

    }

}

操作过程如下，有两个指针i和j，j 指向原来的数组，i 指向新的数组

i++，得i == 1，j++，得 j== 1。

i++，得i == 2，j++，得j == 2。

此时 i == index，则插入新添加的元素。

i++，得i == 3，此时 j 不做自增操作。

i++，得i == 4，j++，得j == 3。

完整代码如下：

public class Two {

    public int[] SortArray(int[] arr,int num) {

        int index = -1;

        int[] arr_copy = new int[arr.length+1];

        // 先定位后插入

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

            if(arr[i] >= num) {

                index = i;

                break;

            }

        }

        if(index == -1) {

            index = arr.length;

        }

        for(int i = 0,j = 0;i<arr_copy.length;i++) {

            // 当i!=index时，即不是要插入的位置，

            if(i != index) {

                arr_copy[i] = arr[j];

                j++;

            }else {

                arr_copy[i] = num;

            }

        }

        return arr_copy;

    }

    public static void main(String[] args) {

        int[] arr = {10,12,45,90};

        // 加入23后依然是升序

        System.out.println("请输入数据:");

        Scanner scanner = new Scanner(System.in);

        int num = scanner.nextInt();

        Two obTwo = new Two();

        arr = obTwo.SortArray(arr, num);

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

            System.out.print(arr[i] + " ");

        }

    }

}

巴特西

java顺序数组插入元素

最新文章

热门文章