根據(jù)索引來(lái)查找元素，也就是獲取對(duì)應(yīng)位置的元素，其復(fù)雜度為O(1)。

public long get(int index){ 
    if(index >= element || index < 0){ 
        throw new ArrayIndexOutOfBoundsException(); 
    }else { 
        return arr[index]; 
    } 
} 

2.4 根據(jù)索引刪除元素刪除對(duì)應(yīng)索引的元素后，我們需要將所有改索引后面的元素，向前移動(dòng)一位。假如我要?jiǎng)h除索引為2的元素，如下：

理論上平均刪除一個(gè)元素，我們需要移動(dòng)N/2次，所以它的時(shí)間復(fù)雜度也為O(1)。

public void delete(int index){ 
    if(index >= element || index < 0){ 
        throw new ArrayIndexOutOfBoundsException(); 
    }else { 
        for (int i = index; i < element; i++) { 
            arr[index] = arr[index+1]; 
        } 
        element --; 
    } 
} 

2.5 修改元素

修改某個(gè)位置的元素，直接根據(jù)索引就一次就可以修改對(duì)應(yīng)的元素，所以它的時(shí)間復(fù)雜度為O(1)。

public void change(int index,long newValue){ 
    if(index >= element || index < 0){ 
        throw new ArrayIndexOutOfBoundsException(); 
    }else { 
        arr[index] = newValue; 
    } 
} 

三 有序數(shù)組

有序數(shù)組是數(shù)組的一種特殊類型，有序數(shù)組中的元素按照某種順序進(jìn)行排列。

3.1 添加元素

在添加元素的時(shí)候，將元素按順序添加到某個(gè)位置。如下，在一個(gè)數(shù)組中添加一個(gè)33的元素。

首先，將索引為3的元素移動(dòng)到索引為4的位置，然后將索引為2的元素移動(dòng)到索引為3的位置，最后將33添加到索引為2的位置。理論上插入一個(gè)元素需要移動(dòng)元素的個(gè)數(shù)為N/2個(gè)，所以它的時(shí)間復(fù)雜度為O(N)。

public void add(long value){ 
    int i; 
    for (i = 0; i < element; i++) { 
        if(arr[i]>value){ 
            break; 
        } 
    } 
 
    for (int j = element; j > i; j--){ 
        arr[j] = arr[j-1]; 
    } 
    arr[i] = value; 
    element++; 
} 

3.2 二分法根據(jù)元素查詢索引

在無(wú)序數(shù)組中，使用線性法進(jìn)行查找相關(guān)元素，線性法即按索引按個(gè)查找。有序數(shù)組可以使用二分法來(lái)查找元素，二分法是指將一個(gè)數(shù)組從中間分成兩個(gè)，判斷元素位于哪個(gè)數(shù)組中，然后重復(fù)這樣的操作。

假如有8個(gè)元素的一個(gè)數(shù)組，數(shù)組內(nèi)容為有序的0-7的序列，要查找5這個(gè)元素，第一次分成0-3和4-7兩個(gè)數(shù)組，然后再將4-7分成4-5和6-7兩個(gè)數(shù)組，最后再將4-5分成4和5就查詢出來(lái)具體的元素了，這樣分割3次就可以查詢出長(zhǎng)度為8的數(shù)組中具體的元素，其復(fù)雜度即為O(logN)(logN在計(jì)算機(jī)中底數(shù)一般指的是2，意思為2的幾次方等于n)。

public int search(long value){ 
    // 中間值 
    int middle = 0; 
    // 最小值 
    int low = 0; 
    // 最大值 
    int pow = element; 
    while (true){ 
        middle = (low + pow) / 2; 
        if(arr[middle] == value){ 
            return middle; 
        }else if (low > pow){ 
            return -1; 
        }else{ 
            if(arr[middle] > value){ 
                pow = middle - 1; 
            }else{ 
                low = middle + 1; 
            } 
        } 
    } 
} 

四 總結(jié)

復(fù)雜度越低意味著算法更加優(yōu)秀，所以O(shè)(1) > O(logN) > O(N) > O(N^2)。

• 無(wú)序數(shù)組插入快，查找和刪除慢
• 有序數(shù)組查找快，插入和刪除慢

本文轉(zhuǎn)載自微信公眾號(hào)「Java旅途」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系Java旅途公眾號(hào)。