無(wú)序數(shù)組

package test;

/**
 * @Author:lanxuebin
 * @Description: 無(wú)序數(shù)組容器類 ；假設(shè)數(shù)組不允許重復(fù)數(shù)據(jù)項(xiàng)
 * @Date: 10:37 2018/8/9
 */
public class DisorderlyArray {
    //內(nèi)置數(shù)組
    private long[] a;
    //已有數(shù)據(jù)項(xiàng)個(gè)數(shù)
    private int nelems;

    /**
     * 構(gòu)造初始化
     * @param max 數(shù)組最大容量
     */
    public DisorderlyArray(int max) {
        a = new long[max];
        nelems = 0;
    }

    /**
     * 插入數(shù)據(jù)項(xiàng);(人為自覺的不要插入重復(fù)數(shù)據(jù)）
     * 插入數(shù)據(jù)項(xiàng)是非?？斓模恍枰徊酵瓿?，由于新的數(shù)據(jù)項(xiàng)總是插入到數(shù)組的第一個(gè)空位上，并且數(shù)據(jù)已有數(shù)據(jù)項(xiàng)個(gè)數(shù)已知，
     * 所以算法知道空位的具體位置，新的數(shù)據(jù)項(xiàng)只是簡(jiǎn)單的插入到下一個(gè)可用的空間。
     * @param value 數(shù)據(jù)項(xiàng)
     */
    public void insert(long value) {
        a[nelems] = value;
        nelems++;
    }

    /**
     * 查詢某個(gè)數(shù)據(jù)項(xiàng)；
     * 查找算法平均需要搜索一半的數(shù)據(jù)項(xiàng)來(lái)查找特定的數(shù)據(jù)項(xiàng)。找數(shù)組頭部的數(shù)據(jù)項(xiàng)快，找數(shù)組尾部的數(shù)據(jù)項(xiàng)慢。
     * 設(shè)數(shù)據(jù)項(xiàng)個(gè)數(shù)為N，則一個(gè)數(shù)據(jù)項(xiàng)的平均查找長(zhǎng)度為N/2。在最壞的情況下，帶查的數(shù)據(jù)項(xiàng)在數(shù)組的最后，
     * 這需要N步才能查到。
     *
     * @param searchkey
     * @return
     */
    public boolean find(long searchkey) {
        int j;
        for(j = 0; j < nelems; j++) {
            if(a[j] == searchkey) {
                break;
            }
        }
        if(j == nelems){
            return false;
        } else {
            return true;
        }
    }

    /**
     * 刪除某個(gè)數(shù)據(jù)項(xiàng)
     * 刪除算法暗含一個(gè)假設(shè)，即非空數(shù)據(jù)項(xiàng)必須連續(xù)存儲(chǔ)，不能有洞。如果允許有洞，那么所有其他的算法都會(huì)變得復(fù)雜。
     * 刪除需要（假設(shè)不允許數(shù)據(jù)項(xiàng)重復(fù)）查找平均N/2數(shù)據(jù)項(xiàng)并平均移動(dòng)剩下的N/2個(gè)數(shù)據(jù)項(xiàng)來(lái)填充刪除而帶來(lái)的洞?？偣睳步。
     * @param value
     * @return
     */
    public boolean delete(long value) {
        int j;
        for(j = 0; j < nelems; j++) {
            if(a[j] == value) {
                break;
            }
        }
        if(j == nelems){
            return false;
        } else {
            for(int k = j; j < nelems; j++) {
                a[k] = a[k+1];
            }
            nelems--;
            return true;
        }
    }

    /**
     * 遍歷所有數(shù)據(jù)項(xiàng)
     */
    public void display() {
        for(int j = 0; j < nelems; j++) {
            System.out.print(a[j] + " ");
            System.out.println("");
        }
    }
}

重復(fù)值問(wèn)題：

允許重復(fù)值條件下的查找算法：

1）匹配一個(gè)，和不允許重復(fù)值一樣平均需要N/2步
2）匹配全部，需要N步

允許重復(fù)值條件下的查找算法：只需一步

允許重復(fù)值條件下的刪除算法：

1）匹配一個(gè)，需要平均N/2步比較和平均N/2步移動(dòng)
2）匹配所有，需要N步比較和（可能）移動(dòng)多于N/2個(gè)數(shù)據(jù)項(xiàng)，這個(gè)操作時(shí)間依賴于重復(fù)數(shù)據(jù)在數(shù)組中的分布情況。

有序數(shù)組

package test;

/**
 * @Author:lanxuebin
 * @Description: 有序數(shù)組
 * @Date: 16:02 2018/8/9
 */
public class OrdArray {
    //內(nèi)置數(shù)組
    private long[] a;
    //已有數(shù)據(jù)項(xiàng)個(gè)數(shù)
    private int nElems;

    /**
     * 構(gòu)造初始化
     * @param max 數(shù)組最大容量
     */
    public OrdArray (int max) {
        a = new long[max];
        nElems = 0;
    }

    /**
     * 插入數(shù)據(jù)項(xiàng)；
     * @param value
     */
    public void insert(long value) {
        //查到當(dāng)前值要插入的位置 平均需要N/2步
        int j;
        for(j = 0; j < nElems; j++) {
            if(a[j] > value) {
                break;
            }
        }
        //后移一位大于當(dāng)前值的數(shù)據(jù) 平均需要N/2步
        for(int k = nElems; k > j; k--) {
            a[k] = a[k-1];
        }
        //插入當(dāng)前值
        a[j] = value;
        //已有數(shù)據(jù)項(xiàng)個(gè)數(shù)加一
        nElems++;
    }

    /**
     * 有序數(shù)組的二分查找  需要log2(N)步
     * @param searchKey
     * @return
     */
    public int find(long searchKey) {
        //當(dāng)前范圍的起始下標(biāo) 初始值為0
        int lowerBound = 0;
        //當(dāng)前范圍的終止下標(biāo) 初始值為數(shù)組的最后一位數(shù)組下標(biāo)
        int upperBound = nElems -1;
        //二分查找當(dāng)前中間值
        int currIn;
        while (true) {
            currIn = (lowerBound + upperBound) / 2;
            if(a[currIn] == searchKey) {
                //如果中間值剛好等于查找值
                return currIn;
            } else if(lowerBound > upperBound) {
                //如果數(shù)組中不存在改值
                return nElems;
            } else {
                if(a[currIn] > searchKey) {
                    //在左半?yún)^(qū) -1是前邊已經(jīng)判斷了是否等于a[currIn]，排除下標(biāo)currIn
                    upperBound = currIn - 1;
                } else {
                    //在右半?yún)^(qū) +1是前邊已經(jīng)判斷了是否等于a[currIn]，排除下標(biāo)currIn
                    lowerBound = currIn + 1;
                }
            }
        }
    }

    /**
     * 刪除某個(gè)值 需要log2(N)+N/2步
     * @param value
     * @return
     */
    public boolean delete(long value) {
        //先查找到改值下標(biāo)
        int i = find(value);
        //沒(méi)有改值
        if(i == nElems) {
            return false;
        } else {
            //前移一位改值后的值
            for(int k = i; i < nElems; i++) {
                a[i] = a[i+1];
            }
            //已有數(shù)據(jù)項(xiàng)個(gè)數(shù)減一
            nElems--;
            return true;
        }
    }

    /**
     * 遍歷所有數(shù)據(jù)項(xiàng)
     */
    public void display() {
        for(int j = 0; j < nElems; j++) {
            System.out.print(a[j] + " ");
            System.out.println("");
        }
    }
}

有序數(shù)組與無(wú)序數(shù)組比較

有序數(shù)組相較無(wú)序數(shù)組來(lái)說(shuō)可以通過(guò)二分查找達(dá)到更快的查找速度，但是由于要維護(hù)有序?qū)е虏迦霐?shù)據(jù)的時(shí)候需要后移所以比無(wú)序數(shù)組慢，由于兩者在刪除時(shí)都需要前移數(shù)據(jù)來(lái)彌補(bǔ)空洞所以刪除都慢。

大O表示對(duì)比：

數(shù)組的缺陷

1）要么查找慢要么插入慢要么刪除慢
2）一旦創(chuàng)建大小固定，不能隨著數(shù)據(jù)項(xiàng)的插入自動(dòng)擴(kuò)展
ps：java中的vector類使用起來(lái)像數(shù)組并且可以擴(kuò)展，但是這種功能是以效率為代價(jià)的。