数组

一、无序数组（假设数组元素不重复）

下面我们建立一个类，对数组的检索、插入、删除、打印操作进行封装

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();
    }

有序数组的优点：查找效率高

有序数组的缺点：删除和插入慢，大小固定