數(shù)組是應(yīng)用最廣泛的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)拜英。它被植入到大部分編程語(yǔ)言中。由于數(shù)組十分易懂，所以它被用來(lái)作為介紹數(shù)據(jù)結(jié)構(gòu)的起步點(diǎn)，并展示面向?qū)ο缶幊毯蛿?shù)據(jù)結(jié)構(gòu)之間的相互關(guān)系揍瑟。
使用數(shù)組
創(chuàng)建數(shù)組
Java中兩種數(shù)據(jù)類型：基本類型和對(duì)象類型蟆盹。在許多編程語(yǔ)言中（如C++）阐滩，數(shù)組也是基本類型坪稽，但在Java中把它們當(dāng)作對(duì)象來(lái)對(duì)待，因此在創(chuàng)建數(shù)組時(shí)必須使用new操作符：
int[] intArray;
intArray = new int[100];
[] 操作符對(duì)編譯器來(lái)說(shuō)是一個(gè)標(biāo)志扛伍，它說(shuō)明正在命名的是數(shù)組對(duì)象而不是普通的變量筷畦。還可以通過(guò)另一種語(yǔ)法來(lái)使用這個(gè)操作符，將它放在變量名的后面刺洒，而不是類型后面：
int intArray[] = new int[100];
但是將[] 放在int后面會(huì)清楚地說(shuō)明[]是數(shù)據(jù)類型的一部分鳖宾，而不是變量名的一部分。
獲取數(shù)組大小
數(shù)組有一個(gè)length字段逆航，通過(guò)它可以得知當(dāng)前數(shù)組大腥撂病（數(shù)據(jù)項(xiàng)的個(gè)數(shù)）：
int arrayLength = intArray.length;
正如大多數(shù)編程語(yǔ)言一樣，一旦創(chuàng)建數(shù)組纸泡，數(shù)組大小便不可改變漂问。
訪問(wèn)數(shù)組數(shù)據(jù)項(xiàng)
數(shù)組數(shù)據(jù)項(xiàng)通過(guò)使用方括號(hào)中的下標(biāo)數(shù)來(lái)訪問(wèn)。這與其他語(yǔ)言類似：
temp = intArray[3];
intArray[7] = 66;
如果訪問(wèn)小于0或比數(shù)組大小大的數(shù)據(jù)項(xiàng)女揭，程序會(huì)出現(xiàn)Array Index Out of Bounds（數(shù)組下標(biāo)越界）的運(yùn)行時(shí)差錯(cuò)誤蚤假。數(shù)組的下標(biāo)是從0開(kāi)始的，也就是說(shuō)第一個(gè)數(shù)據(jù)項(xiàng)的下標(biāo)是0吧兔。
初始化
當(dāng)創(chuàng)建數(shù)組之后磷仰，如果不另行指定，基本類型數(shù)組會(huì)自動(dòng)賦值為0或0.0而對(duì)象數(shù)組會(huì)自動(dòng)賦值為null對(duì)象境蔼。使用下面的語(yǔ)法可以對(duì)一個(gè)基本類型的數(shù)組初始化灶平，賦入非空值：
int[] intArray = {0,3,6,9,12,15};
數(shù)組使用的例子
/**
* HighArray對(duì)數(shù)組基本操作進(jìn)行封裝
*/
public class HighArray {
private long [] a;
private int nElems;
public HighArray(int max){
a = new long[max];
nElems = 0;
}
/**
* 查找
*/
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;
}
}
/**
* 插入
* @param value
*/
public void insert(long value){
a[nElems] = value;
nElems++;
}
/**
* 刪除
* @param value
* @return
*/
public boolean delete(long value){
int j;
for(j = 0; j < nElems;j++){
if(value == a[j]){
break;
}
}
if(j == nElems){
return false;
}else{
// 移動(dòng)后面的元素
for (int k = j; k < nElems;k++){
a[k] = a[k+1];
}
nElems--;
return true;
}
}
/**
* 遍歷數(shù)組元素
*/
public void display(){
for(int j = 0; j < nElems; j++){
System.out.print(a[j]+" ");
}
System.out.println();
}
}
有序數(shù)組
假設(shè)一個(gè)數(shù)組伺通，其中的數(shù)據(jù)項(xiàng)按關(guān)鍵字升序排列，即最小值在下標(biāo)為0的單元上逢享，每一個(gè)單元比前一個(gè)單元的值大罐监。這種數(shù)組被稱為有序數(shù)組。將數(shù)據(jù)按順序排序的好處就是可以通過(guò)二分查找顯著地提高查找速度瞒爬。
當(dāng)向這種數(shù)組中插入數(shù)據(jù)項(xiàng)時(shí)弓柱，需要為插入操作找到正確的位置：剛好在稍小值的后面，稍大值的前面侧但。然后將所有比待插入的數(shù)據(jù)項(xiàng)大的值向后移以便騰出空間矢空。
二分查找
二分查找使用的方法與我們?cè)诤⑼瘯r(shí)期常玩的猜數(shù)游戲中所用的方法一樣。在這個(gè)游戲里禀横，一個(gè)朋友會(huì)讓你猜她正想的一個(gè)1至100之間的數(shù)屁药。當(dāng)你猜來(lái)一個(gè)數(shù)后，它會(huì)告訴你三種選擇中的一個(gè)：你猜的比她想的大柏锄，或小酿箭，或猜中了。
為了能用最少的次數(shù)猜中绢彤，必須從50開(kāi)始猜。如果她說(shuō)你猜得太小蜓耻，則推出那個(gè)數(shù)在51至100之間茫舶，所以下一次猜75。但如果她說(shuō)有些大刹淌，則推出那個(gè)數(shù)在1至49之間饶氏，所以下一次猜25。
每猜一次就會(huì)將可能的值劃分成兩部分有勾。最后范圍會(huì)縮小到一個(gè)數(shù)字那么大疹启，那就是答案。
有序數(shù)組的Java代碼
public class OrdArray {
private long[] a;
private int nElems;
public OrdArray(int max){
a = new long[max];
nElems = 0;
}
public int size(){
return nElems;
}
// 二分查找
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; // can't find it
}else {
if(a[curIn] < searchKey){
lowerBound = curIn + 1;
}else {
upperBound = curIn - 1;
}
}
}
}
public void insert(long value){
int j;
// 找到待插入的位置
for(j = 0; j < nElems;j++){
if(a[j] > value){
break;
}
}
// 騰出空間
for(int k = nElems;k > j;k--){
a[k] = a[k-1];
}
a[j] = value;
nElems++;
}
public boolean delete(long value){
int j = find(value);
if(j == nElems){
return false;
}else{
for (int k = j;k < nElems;k++){
a[k] = a[k+1];
}
nElems--;
return true;
}
}
public void display(){
for(int j = 0; j < nElems; j++){
System.out.print(a[j]+" ");
}
System.out.println();
}
}
