Chp1 Array

创建一个数组HighArray

HighArray中的find()方法 ，用数据项的值作为参数传递，依次查找数组中的每一个数据项。返回值是true或者false，取决于是否找到该数据项。

insert()方法，向数组下一个空位置放置一个新的数据项。一个名为size的字段跟踪记录着数组中实际已有的数据项个数。main()方法不再需要为数组中还有多少数据项而担心。

delete()方法， 查找相应的数据项，当它找到该数据项后，便将所有后面的数据项前移，从而覆盖了待删除的数据项，然后nElem减少一。

dispaly()方法 ， 用来显示数组中所有的数据项的值。

class HighArray{
    private long[] data;    //ref to array data
    private int size;  //number of data items
    
    public HighArray(int max){    //constructor
        data = new long[max];     //creat the array
        size = 0;                 //no items yet
    }
    public boolean find(long searchKey){ //find specified value
        int j;                    
        for(j=0;j<nElems;j++){        //for each elements     
            if(data[j] == searchKey)  //found items?
                break;                //exit loop before end gone to end?
        }
        if(j == size)           
            return false;          //can't found it
        else
            return true;           // found it
    }
     public void insert(long value){ //put elements into array 
         data[size] = value;         //insert it
         nElems ++;                  //increamnt size 
     }
    public boolean delete(long value){
        int j;
        for (j=0 ;j<size ;j++)     //look for it
            if(value == a[j])      
                break;
        if(j == size)
            return false;          //can't find it
        else
            for(int k=j;k< size;k++)
                a[k] = a[k+1];      //move higher ones down
            size--;                 //decrement size
            return true;
    }  
    public void display(){
        for(int j =0;j<nElems;j++)        //for each elements
            System.out.println(a[j]+" "); //display for it
    }
}

add(int index,int e) 方法：把元素添加到指定位置。

1、先判断index是否越界，若越界则抛出异常。

2、如果数组元素个数与长度相等，则需要扩容。

3、通过循环，把数组中从最后一位到index位置的元素都向后挪动一位

4，再把index位置中的元素赋值成e。元素数量增加

public void add(int index,int e){
    //先判断index是否越界
    if(index < 0|| index> size)
        throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
    //如果数组元素个数与长度相等，需要扩容
    if(size == data.length)
        resize(2*data.length);
    //把数组中从最后到index位置的元素都向后挪动一位，再把index位置中的元素赋值成e
    for(int i = size; i >= index ;i--)
        data[i+1] = data[i];
    data[index] = e;
    size++;
}

resize(new capacity)方法：进行数组扩容。新建一个新数组newData,把旧数组中元素都赋值给新数组，最后把引用变量指向新数组。

public void resize(int capacity){
    int[] newData = new int[capacity];
    for(int i = 0;i< size; i++)
        newData[i] = a[i];
    a = newData;
}

remove(int index)方法: 删除指定index位置的元素。画图来理解下标范围 。

public int remove(int index){
    if(index <0 || index>size)
        throw new IllegalArgumentException("Remove failed. Index is illegal.");
    //保存要删除位置的元素，以便返回
    int ret = data[index];
    //从下标index+1开始到size-1，用后一个位置的元素去覆盖前一个位置的元素，就把index位置元素挤出去了。
    for(int i = index+1;i<size;i++)
        data[i-1] = data[i];
    size--;
    
    //为了避免数组空间有所浪费，因此进行缩容
    if(size == data.length/2)
        resize(data.length/2);
    return ret;
}

removeElement(int e)方法: 从数组中删除指定元素。通过find()方法找到该元素所对应的下标，然后调用remove()方法

public void removeElement(int e){
    int index = find(e);
    if(index != -1)//如果没有找到
        remove(index);
}

重写toString() 方法。

1，创建StringBuilder实例

@Override
public String toString(){
      StringBuilder res = new StringBuilder();
      res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
      res.append('[');
      for(int i = 0 ; i < size ; i ++){
          res.append(data[i]);
          if(i != size - 1)         //如果不是最后一个元素
              res.append(", ");
        }
      res.append(']');
      return res.toString();
}

二分查找中的find()方法

二分查找用于有序数组。通过将数组数据项范围不断对半分割来查找特定的数据项。

在一开始设变量lowerBound和upperBound指向数组的第一个和最后一个非空数据项，来确定查找searchKey数据项的范围。然后在while循环中，当前下标curIn被设置为这个范围中间值。

循环中每次将范围缩小一半，最终这个范围会小到无法再分割。在下一条语句中会判断。如果lowerBound比upperBound大，则范围已经不存在了。

public int find(long searchKey){
    int lowerBound = 0;
    int upperBound = nElems-1;
    int curIn;
    while(true){
        curIn = (lowerBound+upperBound)/2;
        if(a[curIn] == searchKey)
            return curIn;
        else if(lowerBound>upperBound)
            return nElems;
        else{
            if(a[curIn]<searchKey)
                lowerBound = curIn+1;  //it's in upper half
            else
                upperBound = curIn -1; //it's in lower half
        }
    }
}

大O表示法

算法	大O表示法的运行时间
线性查找	O(N)
二分查找	O(logN)
无序数组的插入	O(1)
有序数组的插入	O(N)
无序数组的删除	O(N)
有序数组的删除	O(N)

小结

Java中的数组是对象，由new操作符创建

无序数组可以提供快速的插入，但查找和删除较慢

将数组封装到类中可以保护数组不被随意更改

类的接口由类的用户可以访问的方法组成

有序数组可以使用二分查找

线性查找需要的时间与数组中数据项的个数成正比

二分查找需要的时间与数组中数据项的个数的对数成正比

大O表示法为比较算法的速度提供了一种更方便的方法

O(1)级时间算法是最友好的，O(logN)次之，O(N)为一般，O(N^2)最差。