时间长度：执行算法的时间长度与执行步数成正比，所以数组的查找算法时间(N/2步)要比插入算法(一步)长很多。删除(不允许重复)查找算法时间(N/2)加上移动剩下N/2个数据项，总共是N步。
允许重复的查找算法：即使找到了上一个，还得继续查找下一个，直到最后一个数据项。但是删除的话，需要检查N个数据项和移动大于等于N/2个数据项。这个操作的平均时间依赖于重复数据项在整个数组中的分布情况。算法的实现：
每删除一个，就将其后的所有数据往前移一位，然后再从头开始查找？
感觉不用从头开始，而应该从查找到的那位开始，这样效率会高一点。
更好的做法是删除完了所有的关键字之后再进行整合？好像不太好实现。
有序与无序数组的对比
1、插入操作慢，因为需要排序
2、查找快，因为有了排序
3、删除稍快，因为查找快
数组实现
```/**
* @author darren
* @time 2020/5/24
* @todo 有序数组
**/
public class OrdArray<T extends Comparable<? super T>> {
private int size;
private T[] tArray;
/**
* 指向当前索引的下一个位置
*/
private int index;
/**
* 是否允许重复
*/
private boolean isDup;
/**
* 默认不允许重复
*
* @param array
*/
public OrdArray(T[] array) {
this.tArray = array;
size = tArray.length;
this.isDup = false;
}
public OrdArray(T[] array, boolean isDup) {
this.tArray = array;
size = tArray.length;
this.isDup = isDup;
}
/**
* 1、找到要插入的位置
* 2、从该位置到末尾都需要往后挪动一位
* 3、在该位置赋value值
*
* @param value
* @return
*/
public int add(T value) {
/**
* 不允许重复，并且在数组中有对应的值，直接返回-1
*/
if (!isDup && getKey(value) != -1) {
return -1;
}
int pos = getPosition(value, 0, index);
/**
* 不是在数组最后一位插入的，都需要挪动
*/
if (pos != index) {
System.arraycopy(tArray, pos, tArray, pos + 1, index - pos);
}
//先挪动一位，再赋值
tArray[pos] = value;
index++;
return pos;
}
/**
* 有序数组中的二分法查找，不再是线性查找
*
* @return 索引位置，-1代表没有找到
*/
public int getKey(T value) {
/**
* 数组为空，直接返回；
* 比最小值小，比最大值大，直接返回，不用二分法查找
*/
if (index < 1 || (tArray[0].compareTo(value) > 0 || tArray[index - 1].compareTo(value) < 0)) {
return -1;
}
return getKey(value, 0, index);
}
/**
* 根据索引位置删除
*
* @param pos
* @return 当前位置下的值
*/
public T delete(int pos) {
if (pos < 0 || pos >= index) {
return null;
}
T value = tArray[pos];
System.arraycopy(tArray, pos + 1, tArray, pos, index - pos - 1);
tArray[index - 1] = null;
index--;
return value;
}
public int delete(T value) {
int pos = getKey(value);
if (pos != -1) {
System.arraycopy(tArray, pos + 1, tArray, pos, index - pos - 1);
tArray[index - 1] = null;
index--;
}
return pos;
}
/**
* 二分法查找算法
*
* @param value
* @param sPos
* @param ePos
* @return
*/
private int getKey(T value, int sPos, int ePos) {
return binarySearch(value, sPos, ePos, true);
}
/**
* 二分法查找，不管存不存在，都返回一个插入的索引值
*
* @param value
* @param sPos
* @param ePos
* @return
*/
private int getPosition(T value, int sPos, int ePos) {
//等于小于最小值，返回0，数组所有的数据后移一位
if (index < 1 || tArray[0].compareTo(value) >= 0) {
return 0;
}
//大于等于最大值，返回当前索引的下一位
if (tArray[index - 1].compareTo(value) <= 0) {
return index;
}
return binarySearch(value, sPos, ePos, false);
}
/**
* 二分算法核心实现
*
* @param value
* @param sPos
* @param ePos
* @param isFind 是否需要真正找到value对应的索引
* @return
* @Todo 递归中return与非return的区别
* 假设某个递归方法有返回值：
* 递归中之所以使用return是用来返回最终执行的那个方法的返回值
* 如果不使用return，那么返回值是首次进入该方法时的返回值
*/
private int binarySearch(T value, int sPos, int ePos, boolean isFind) {
/**
* @todo 这个查找终止条件很关键
*/
if (sPos > ePos) {
return isFind ? -1 : (ePos + 1);
}
int pos = (sPos + ePos) / 2;
/**
* 发现值比数组的中间值小
* @Todo 关键在于pos-1和pos+1
*/
int compRlt = tArray[pos].compareTo(value);
if (compRlt > 0) {
//去掉return会导致返回的值是首次进入该方法时的返回值
return binarySearch(value, sPos, pos - 1, isFind);
} else if (compRlt < 0) {
return binarySearch(value, pos + 1, ePos, isFind);
}
return pos;
}
/**
* 正向排序
* 1、首先决定内层循环的算法
* 2、决定外层循环的次数：从最后开始比最前开始要好
* 不要内层外层一起考虑
*/
public void bubbleSort() {
for (int i = index - 1; i > 0; i--) { //只是用来控制次数，所以可前可后
for (int j = 0; j < i; j++) {
if (tArray[j] > tArray[j + 1]) {
swap(j, j + 1);
}
}
}
}
/**
* 选择排序算法精髓:
* 和冒泡算法一样比较，但只是比较，找到最小值，直到比较完一次后后才进行交换
* 然后进行下一次比较，并且比较的个数少了一个
*/
public void selectSort() {
for (int i = 0; i < index; i++) {
int min = tArray[i];
//pos的初始值很重要
int pos = i;
for (int j = i + 1; j < index; j++) {
if (min > tArray[j]) {
min = tArray[j];
pos = j;
}
}
//此处的交换是放在内层循环的外面，因此减少了交换的次数
swap(i, pos);
}
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[");
for (T t : tArray) {
sb.append(t);
sb.append(",");
}
sb.delete(sb.length() - 1, sb.length());
sb.append("]");
return sb.toString();
}
public static void main(String[] args) {
Integer[] ints = new Integer[10];
OrdArray<Integer> ordArray = new OrdArray<Integer>(ints, true);
ordArray.add(5);
ordArray.add(1);
ordArray.add(7);
ordArray.add(0);
ordArray.add(9);
ordArray.add(6);
ordArray.add(6);
int i1 = ordArray.getKey(1);
int i2 = ordArray.getKey(9);
int i3 = ordArray.getKey(3);
int i4 = ordArray.delete(new Integer(7));
int i5 = ordArray.delete(new Integer(0));
int i6 = ordArray.delete(new Integer(9));
Integer int1 = ordArray.delete(0);
Integer int2 = ordArray.delete(3);
}
}```
数组不能满足插入删除查询都很快的要求。
为什么不将所有的数据用数组来存储
插入效率太低(有序数组)，查找、删除效率太低(无序)
另外，数组大小是固定的。
网友评论