Question

JAVA算法, 看看有什么做法;

题目：有一个已经排好序的数组。现输入一个数，要求按原来的规律将它插入数组中。 int[] a = new int[]{1, 2,6, 14, 25, 36, 37,55};

Answer 1

二分插入排序

Answer 2

因为你用到了数组，所以每次插入的时候都需要重新分配空间，而且没法用二分法进行查找和插入。

其实还有两种更好的解决方案：

1. 将所有数字都读完，然后进行排序

2. 读数字前，先确定一共有多少个数字，然后分配充足的空间，这时就可通过二分法进行查找，但还是避免不了大量数据的移动。

int insert(int[]a, int num)

{

 int[]temp = new int[a.length + 1];

 int i = 0;

 while(a[i] < num)

 {

  temp[i] = a[i];

  ++i;

 }

 temp[i] = num;

 while(i < a.length)

 {

  temp[i + 1] = a[i];

  ++i;

 }

 a = temp;

}