數據結構與算法2——數組

　　數組是應用最廣泛的數據存儲結構。它被植入到大部分編程語言中。大部分數據結構都有最基本的四個操作：插入、刪除、查找、修改。對于這四種操作每一種數據結構都有相應的算法。算法和數據結構因此就是非常緊密的相聯系的。

1 數組例子 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

　　數組的每一個元素必須是連續，也就是中間沒有洞。就是說第一個元素和第三個元素有值，但不允許第二個元素是空的。

package chapter2;

public class Array {
    public static void main(String[] args){
        //創建一個數組
        long[] arr;
        arr = new long[100];
        int nElems = 0;
        int j;
        long searchKey;
        arr[0] = 99;
        arr[1] = 11;
        arr[2] = 22;
        arr[3] = 33;
        arr[4] = 55;
        arr[5] = 66;
        arr[6] = 44;
        arr[7] = 77;
        arr[8] = 23;
        arr[9] = 88;
        nElems = 10;
        //輸出前10位數組元素
        for(j = 0; j < nElems; j++){
            System.out.print(arr[j] + " ");
        }
        System.out.println();
        //查找數組的一個元素值為55的元素
        searchKey = 55;
        for(j = 0; j < arr.length; j++){
            if(arr[j] == searchKey){
                break;
            }
        }
        if(j == nElems){
            System.out.println("Can't find the element");
        }else{
            System.out.println("find the element " + searchKey + " at index " + (j + 1) );
        }
        //刪除指定元素
        searchKey = 66;
        for(j = 0; j < arr.length; j++){
            if(arr[j] == searchKey){
                break;
            }
        }
        for(int k = j; k < nElems; k++){
            arr[k] = arr[k+1];
        }
        nElems--;
        //輸出刪除后的數組
        for(j = 0; j < nElems; j++){
            System.out.print(arr[j] + " ");
        }
    }
}

輸出結果：
99 11 22 33 55 66 44 77 23 88 
find the element 55 at index 5
99 11 22 33 55 44 77 23 88 

2 將程序劃分成類 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

上面的程序包含了一個很大的方法，通過將程序劃分成類以后，并且將其中的方法模塊化，這樣程序看起來更加有條理。

package chapter2;
class ArrayMethod{
    private long[] arr;
    private int nElems;
    public ArrayMethod(int max){
        arr = new long[max];
        nElems = 0;
    }
    public void insert(long value){
        arr[nElems] = value;
        nElems++;
    }
    public boolean find(long searchKey){
        //查找數組的一個元素值為searchKey的元素
        int j;
        for(j = 0; j < arr.length; j++){
            if(arr[j] == searchKey){
                break;
            }
        }
        if(j == nElems){
            return false;
        }else{    
            return true;
        }
    }
    //刪除指定元素
    public boolean delete(long searchKey){
        int j;
        for(j = 0; j < arr.length; j++){
            if(arr[j] == searchKey){
                break;
            }
        }
        for(int k = j; k < nElems; k++){
            arr[k] = arr[k+1];
        }
        nElems--;
        return true;
    }
    //輸出數組
    public void display(){
        //輸出前10位數組元素
        for(int j = 0; j < nElems; j++){
            System.out.print(arr[j] + " ");
        }
        System.out.println();
    }
}
class HighArray {

    public static void main(String[] args){
        int maxSize = 100;
        ArrayMethod arr = new ArrayMethod(maxSize);
        arr.insert(99);
        arr.insert(11);
        arr.insert(22);
        arr.insert(33);
        arr.insert(55);
        arr.insert(66);
        arr.insert(44);
        arr.insert(77);
        arr.insert(23);
        arr.insert(88);
        //輸出數組
        arr.display();
        //查找值為55的元素
        long searchKey = 55;
        if(arr.find(searchKey)){
            System.out.println("find the element ");
        }else{
            System.out.println("Can't find the element");
        }
        //刪除指定元素
        searchKey = 22;
        if(arr.delete(searchKey)){
            System.out.println("Delete the element successfully ");
        }else{
            System.out.println("Can't find the element");
        }
        //輸出刪除元素后的數組
        arr.display();
    }
}

3 有序數組 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

　　假設一個數組，其中的數據項按關鍵字升序排列，即最小值在下標為0的單元上，每一個單元都比前一個單元的值大。這種數組被稱為有序數組。

　　當向這種數組中插入數據項時，需要為插入操作找到正確的位置：剛好在稍小值的后面，稍大值的前面。然后將所有比待茶數據項的值向后移以便騰出空間。
　　將數據按順序排列的好處之一就是可以通過二分法查找顯著地提高查找速度。但缺點是降低了插入操作的速度。

4 線性查找 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

　　默認情況下是線性查找，線性查找和未經排序的數組的查找操作相似。

5 二分查找 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

　　當使用二分查找時就體現有序數組的好處，這種查找比線性查找快很多，尤其是對大數組來說更為顯著。
　　二分查找首先從要查找的范圍確定一個中位數，然后比較要找的數和中位數的大小關系，確定更小的范圍，依次遞歸，知道找到那個數。

?

?

?將數目進行放大，可以發現二分查找是極為優秀的

5.1 有序數組的二分搜索代碼 ??

二分查找是將數組數據項范圍不斷對半分隔來查找特定的數據項。方法如下所示：

package chapter2;
class ArrayMethod{
    private long[] arr;
    private int nElems;
    public ArrayMethod(int max){
        arr = new long[max];
        nElems = 0;
    }
    public void insert(long value){
        arr[nElems] = value;
        nElems++;
    }
    //二分查找法
    public int halfFind (long searchKey){
        int lowerBound = 0;
        int upperBound = nElems - 1;
        int curIn;
        while(true){
            curIn = (lowerBound + upperBound)/2;
            if(arr[curIn] == searchKey){
                return curIn;
            }else if(lowerBound >= upperBound){
                return nElems;
            }else{
                if(arr[curIn] > searchKey){
                    upperBound = curIn - 1;
                }else{
                    lowerBound = curIn + 1;
                }
            }    
        }
    }
    public int size(){
        return nElems;
    }
    public boolean find(long searchKey){
        //查找數組的一個元素值為searchKey的元素
        int j;
        for(j = 0; j < arr.length; j++){
            if(arr[j] == searchKey){
                break;
            }
        }
        if(j == nElems){
            return false;
        }else{    
            return true;
        }
    }
    //刪除指定元素
    public boolean delete(long searchKey){
        int j;
        for(j = 0; j < arr.length; j++){
            if(arr[j] == searchKey){
                break;
            }
        }
        for(int k = j; k < nElems; k++){
            arr[k] = arr[k+1];
        }
        nElems--;
        return true;
    }
    //輸出數組
    public void display(){
        //輸出前10位數組元素
        for(int j = 0; j < nElems; j++){
            System.out.print(arr[j] + " ");
        }
        System.out.println();
    }
}
class HighArray {

    public static void main(String[] args){
        int maxSize = 100;
        ArrayMethod arr = new ArrayMethod(maxSize);
        arr.insert(99);
        arr.insert(11);
        arr.insert(22);
        arr.insert(33);
        arr.insert(55);
        arr.insert(66);
        arr.insert(44);
        arr.insert(77);
        arr.insert(23);
        arr.insert(88);
        //輸出數組
        arr.display();
        //查找值為55的元素
        long searchKey = 35;
//        if(arr.find(searchKey)){
//            System.out.println("find the element ");
//        }else{
//            System.out.println("Can't find the element");
//        }
        //二分法查找
        if(arr.halfFind(searchKey) != arr.size()){
            System.out.println("Find it");
        }else{
            System.out.println("Can't find it");
        }
//        //刪除指定元素
//        searchKey = 22;
//        if(arr.delete(searchKey)){
//            System.out.println("Delete the element successfully ");
//        }else{
//            System.out.println("Can't find the element");
//        }
        //輸出刪除元素后的數組
        arr.display();
    }
}

5.2 有序數組的優點 ? ? ? ? ? ? ?

　　使用有序數組最主要的好處是查找的速度比無序數組快多了。不好的方面是在插入操作中由于所有靠后的數據都需要移動以騰開空間，所以速度較慢。有序數組和無序數組中的刪除操作都很慢，這是因為數據項必須向前移動來填補已刪除數據項的洞。有序數組在查找頻繁的情況下十分有用，但若是插入和刪除較為頻繁時，則無法高效工作。

6 大O表示法 ? ? ? ? ? ? ? ? ? ??

　　計算機科學中評價算法效率的方法稱為大O表示法。比較算法時候通常會說"算法A比算法B快2倍"，這種說法意義不大。因為數據項的變化會對排序造成一定很大影響。有可能數據項增加50%，算法A就比B快了3倍，或者可能只有一半的數據項，A和B的速度是相同的。

6.1 無序數組的插入：常數 ? ??

　　無序數組的插入是我們到現在為止所見過的算法中唯一一個與數組項個數無關的算法。新數據項總被放在下一個有空的地方,a[nElems]，然后nElems增加。無論數組中的數據項個數N有多大，一次插入總是用相同的時間。我們可以說向一個無序數組中插入一個數據項的時間T是一個常數K
T=K
在現實情況中，插入所需的實際時間與以下這些因素有關：微處理器，編譯程序生成程序代碼的效率，等等。

6.2 線性查找：與N成正比 ? ??

　　在數組數據項的線性查找中，我們已經發現尋找特定數據項所需的比較平均次數為數據項總數的一半。因此設N為數據項總數，搜索時間T與N的一半成正比：
T=K*N/2
　　同插入一樣，若要得到方程中K的值，首先需要對某個N值的查找進行計時，然后用T來計算K。當得到K后，便可以對任意N的值來計算T。將2并入K可以得到更方便的公式，新K值等于原先的K除以2即
T=K*N
這個方程說明平均線性查找時間與數組的大小成正比。即如果一個數組增大兩倍，則所花費的查找時間也會相應地增長兩倍。

6.3 二分查找:與log(N)成正比

　　同樣，我們可以為二分查找指定出一個與T和N有關的公式:T=K*log2(N)
　　實際上，由于所有的對數和其他對數成比例(比如從底數2轉換到底數為10需乘以3.322)，也可以將這個為常數的底數也并入K。由此不必指定底數:
T=K*log(N)
不要常數
　　大O表示法同上面的公式比較類似，但它省去了常數K。當比較算法時，并不在乎具體的微處理器或編譯器；真正需要比較的是對應不同的N值，T是如何變化的，而不是具體的數字，因此不需要常數。
　　大O表示法使用大寫字母O，可以認為其含義是order of(大約是)。我們可以使用大O表示法來描述線性查找使用了O(N)級時間，二分查找使用了O(logN)級時間。向一個無序數組中的插入使用了O(1)，或常數級時間。

下表總結的是討論過的算法的運行時間

　　大O表示法的實質并不是對運行時間給出實際值，而是表達了運行時間是如何受數據項個數所影響的。除了實際安裝后真正去測量一次算法的運行時間之外，這可能是對算法進行比較的最有意義的方法了。

6.4 幾種算法時間復雜度的對比?

?

7 為什么不用數組表示一切？ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

　　僅使用數組似乎就可以完成所有工作，為什么不用它們來進行所有數據存儲呢？我們已經見到了許多關于數組的缺點。在一個無序數組中可以很快進行插入(O(1))，但是查找卻要花費較慢的O(N)時間。在一個有序數組中可以查找得很快，用O(logN)的時間，但插入卻花費了O(N)時間。對于這兩種數組而言，由于平均半數的數據項為了填補"空洞"必須移動，所以刪除操作平均需要O(N)時間。
　　如果有一種數據結構進行任何如插入、刪除和查找的操作都很快(理想的O(1)或是O(logN)時間)，那就好了。后面我們會介紹類似的數組，但這是以程序的復雜度為代價的。
　　另外數組被創建后，占用內存長度是確定的，無法進行修改，這樣的話，如果創建的長度過大，但是實際需要的很少就會造成內存浪費，如果創建的長度過小，就會造成溢出，無法彈性使用。