查找速度比无序数组快多了
插入时要按排序方式把后边的数据进行移动。
删除数据时必须把后边的数据向前移动来填充删除项的空缺。
ArrayInterface.java
package com.arithmetic.array;
import java.util.Arrays;
/**
* Created by baiguantao on 2017/10/17.
*/
public interface ArrayInterface {
void insert(int val);//插入
int find(int val);//查找
int size();//已有元素数量
void del(int val);//删除
/**
* 默认显示array方法
* @param arr
*/
default void displayAll(int[] arr){
int total=size();
Arrays.stream(arr).limit(total).forEach(a->{
System.out.println(a);
});
}
}
OrderArray.java
package com.arithmetic.array;
/**
* Created by baiguantao on 2017/10/17.
* 有序数组
*/
public class OrderArray implements ArrayInterface{
public int[] arr;
public int size;//已有元素数量
public OrderArray(int maxsize) {
this.arr = new int[maxsize];
size=0;
}
/**
* 这里是有序数组
* 线性查找示例
* 找到当前元素适合插入的问题
* 随后对元素进行移动操作
* @param val
*/
@Override
public void insert(int val) {
//查找适合的位置
int realpostion=0;
for (realpostion=0;realpostion<size;realpostion++) {
if(arr[realpostion]>val)break;//如果当前元素比val大,则终止循环(这里默认是有序递增形式数组)
}
//进行元素置换 k是元素数量 比下标错开1位 下标从0 开始 所以k 其实对应下标+1 这样子
for (int k=size;k>realpostion;k--) {
arr[k]=arr[k-1];
}
arr[realpostion]=val;
size++;
}
/**
* 二分查找
* @param val
* @return
*/
@Override
public int find(int val) {
int first=0;//二分当前范围的起始位置
int last=size-1;//二分当前范围的结束位置
int mid;//二分当前范围的中间值
while (true){
mid=(first+last)/2;
if (arr[mid]==val) {//如果刚好与查找的一致,则返回下标
return mid;
}else if (first>last){//未查到则返回数组大小
return size;
}else{
//当前值大于中间下标
if (arr[mid]<val) {
first=mid+1;
}else{
last=mid-1;
}
}
}
}
@Override
public int size() {
return size;
}
/**
* 数组删除 并移动数组元素
* @param val
*/
@Override
public void del(int val) {
int valindex=find(val);
if (valindex==size) {//未查到下标
System.out.println("未查到");
}else{
for (int k=valindex;k<size;k++) {//移动后边数组
arr[k]=arr[k+1];
}
size--;
System.out.println("查到了,进行数组移动...");
}
}
static boolean b;
public static void main(String[] args) {
OrderArray orderArray=new OrderArray(10);
orderArray.insert(3);
orderArray.insert(6);
orderArray.insert(5);
orderArray.insert(4);
orderArray.insert(1);
orderArray.displayAll(orderArray.arr);
orderArray.del(4);
orderArray.displayAll(orderArray.arr);
/* int x=0;
if (b) {
x=1;
}else if (b=false) {
x=2;
}else if (b) {
x=3;
}else {
x=4;
}
System.out.println("x:"+x);*/
}
}
其实我们默认使用的就是线性查找。虽然也可以实现查找,但是时间复杂度是N,相对来说比较耗时。 我们在插入的时候采用线性方式来实现。如下所示:
/**
* 这里是有序数组
* 线性查找示例
* 找到当前元素适合插入的问题
* 随后对元素进行移动操作
* @param val
*/
@Override
public void insert(int val) {
//查找适合的位置
int realpostion=0;
for (realpostion=0;realpostion<size;realpostion++) {
if(arr[realpostion]>val)break;//如果当前元素比val大,则终止循环(这里默认是有序递增形式数组)
}
//进行元素置换 k是元素数量 比下标错开1位 下标从0 开始 所以k 其实对应下标+1 这样子
for (int k=size;k>realpostion;k--) {
arr[k]=arr[k-1];
}
arr[realpostion]=val;
size++;
}
使用二分查找的前提是数据是有序的 我们在查找的方法中用二分查找的方式来实现
/**
* 二分查找
* @param val
* @return
*/
@Override
public int find(int val) {
int first=0;//二分当前范围的起始位置
int last=size-1;//二分当前范围的结束位置
int mid;//二分当前范围的中间值
while (true){
mid=(first+last)/2;
if (arr[mid]==val) {//如果刚好与查找的一致,则返回下标
return mid;
}else if (first>last){//未查到则返回数组大小
return size;
}else{
//当前值大于中间下标
if (arr[mid]<val) {
first=mid+1;
}else{
last=mid-1;
}
}
}
}