一、无序数组（假设数组元素不重复）
下面我们建立一个类，对数组的检索、插入、删除、打印操作进行封装
public class Array {
private int[] ints;
private int length;//数组中真实数据长度
private int maxSize;//初始化数组长度
public Array(int maxSize) {
ints = new int[maxSize];
this.maxSize = maxSize;
length = 0;
}
public boolean isFull(){
return length == maxSize ? true:false;
}
public void insert(int value) throws Exception {
if (isFull()){
throw new Exception("数组溢出");
}
ints[length] = value;
length++;
}
//判断数组中是否含有某一个元素：是：返回下标，否：返回-1
public int contains(int elem){
for (int i =0;i<length;i++){
if (ints[i] == elem){
return i;
}
}
return -1;
}
public boolean delete(int value){
int location;
if ((location = contains(value))!=-1){
for (int i = location;i<length;i++){
ints[i] = ints[i+1];
}
length--;
return true;
}else {
return false;
}
}
public void display(){
for (int i= 0;i<length;i++){
System.out.print(ints[i]+" ");
}
System.out.print("\n");
}
}
//测试
public static void main(String[] args) throws Exception {
Array array=new Array(5);
array.insert(1);
array.insert(2);
array.insert(3);
array.insert(4);
array.display();
array.delete(3);
array.display();
array.insert(70);
array.display();
System.out.print(array.contains(1));
}
无序数组的优点：插入快，如果知道下标，可以很快的存取
无序数组的缺点：查找慢，删除慢，大小固定。
二、有序数组(假设数组元素升序)
所谓的有序数组就是指数组中的元素是按一定规则排列的，其好处就是在根据元素值查找时可以是使用二分查找，查找效率要比无序数组高很多，在数据量很大时更加明显。当然缺点也显而易见，当插入一个元素时，首先要判断该元素应该插入的下标，然后对该下标之后的所有元素后移一位，才能进行插入，这无疑增加了很大的开销。
因此，有序数组适用于查找频繁，而插入、删除操作较少的情况
public class OrderArray {
private int[] ints;
private int maxSize;
private int length;
public OrderArray(int maxSize) {
ints = new int[maxSize];
length = 0;
this.maxSize = maxSize;
}
// 用二分查找法定位某个元素，如果存在返回其下标，不存在则返回-1
public int find(int target) {
int leftBound = 0;
int rightBound = length - 1;
int curIn;
if (rightBound < 0) {
return -1;
}
while (true) {
curIn = (rightBound + leftBound) / 2;
//一个元素
if (ints[curIn] == target) {
return curIn;
}
//两个元素
if (curIn == leftBound) {
if (target == ints[leftBound]) {
return leftBound;
} else {
if (target == ints[rightBound]) {
return rightBound;
} else {
return -1;
}
}
} else {
//至少三个元素
if (target > ints[curIn]) {
leftBound = curIn;
} else {
rightBound = curIn;
}
}
}
}
// 插入
public void insert(int elem) throws Exception {
int location = 0;
if (isFull()){
throw new Exception("数组溢出");
}
for (;location <length;location++){
if (elem < ints[location]){
break;
}
}
for (int i =length;i > location;i--){
ints[i] = ints[i-1];
}
ints[location] = elem;
length++;
}
//判断数组是否满
public boolean isFull(){
return length == maxSize? true:false;
}
// 删除某个指定的元素值，删除成功则返回true，否则返回false
public boolean delete(int value) {
int location;
if ((location = find(value)) != -1){
for (int i=location ; i<length-1;i++){
ints[i] = ints[i+1];
}
length--;
return true;
}
return false;
}
// 列出所有元素
public void display() {
for (int i= 0;i<length;i++){
System.out.print(ints[i]+" ");
}
System.out.print("\n");
}
}
//测试
public static void main(String[] args) throws Exception {
OrderArray orderArray = new OrderArray(4);
orderArray.insert(3);
orderArray.insert(4);
orderArray.insert(6);
orderArray.insert(8);
int i = orderArray.find(8);
System.out.println("在数组中的下标是" + i);
if (orderArray.delete(4)) {
orderArray.display();
}
orderArray.insert(1);
orderArray.display();
}
