什麼是數組
首先明確,數組是一個很重要的內容,非常重要。
前面介紹的if結構、循環,解決的都是算法問題。那什麼是算法?所謂算法就是流程,像取錢怎麼取?插卡,輸入密碼,輸入要取錢的金額,確定。那這個過程,第一步怎麼做,第二步怎麼做,判斷還是循環,這就是算法。
Pascal之父Nicklaus Wirth說過一句話並因此而得了圖靈獎,這句很經典的話就是,程序即為:算法+數據結構,所謂數據結構,簡單的說就是把數據按照特定的某種結構來保存,設計合理的數據結構是解決問題的前提條件。今天講的數組,就是最基本的、用得最多的一種數據結構。試想下,存儲一個學員的成績,可以聲明一個整型變量score來存儲,聲明20個學員的考試成績呢?存儲50個隨機數呢?存儲1萬個帳號呢?聲明太多的變量,顯然很繁瑣,並且不適合整體的操作。像這種情況,可以使用數組這種數據結構來解決。
數組為相同數據類型的元素組成的集合,數組元素按線性順序排列,所謂線性順序是指除第一個元素外,每一個元素都有唯一的前驅元素;除最後一個元素外,每一個元素都有唯一的後繼元素(“一個跟一個”),可以通過元素所在位置的順序號(下標)做標識訪問每一個元素(下標從0開始,最大到元素個數-1),數組結構如下圖 - 2所示:
從上圖中可以看出,a[0]即代表第1個元素,a[1]代表第二個元素,假設數組有5個元素,則最後一個元素即為a[5-1]。
數組的定義
聲明數組的語法為: 數據類型[] 數組名 = new 數據類型 [ 大小 ] ;示例代碼如下:
int [] arr = new int[10] ;
上面的示例代碼中,int[]為數組類型,表示數組中的每一個元素為int類型;數組也是在內存中用於存儲數據的,並且是存儲一組數據,同樣需要一個對它的引用,該引用即為arr,arr稱為數組類型變量(引用);new為特定的聲明數組的關鍵字,後面會詳細講解,現在先記住。數組的聲明必須要有元素個數,10即為數組中元素的個數,也稱為數組長度。總結下來, 定義基本類型數組的要點包括:
確切的數據類型:用於開闢空間大小
整體的數組名字:用於對數據的引用
不能缺少的“ [ ] ”
注意在定義數組時使用的new關鍵字, 正是因為new語句,才使得數組分配到了指定大小的空間(後面詳細講解)。聲明數組的時候,int[] arr 與 int arr [] 兩種寫法均可。常用方式為int[] arr。聲明數組時不規定數組長度(可以看到聲明時僅指定了int[],未指定長度),new關鍵字分配空間時需指定分配的空間大小(new int[10])。
數組的初始化
基本類型 (數據元素為基本類型)的數組創建後,默認為其數組元素設置了初始值,元素的初始值如下所示:byte、short、char、int、long為0; float和double為0.0; boolean為false。注意,此處強調的是基本類型數組的默認值,後期會介紹數據元素為非基本類型的,它的默認初始值與基本類型不同。
在程序中很多時候需要手動設置初始值,可以在數組聲明的同時進行初始化,如下代碼所示:
int [ ] arr = { 10,23,30,-10,21 } ;
上面的代碼中,元素的個數即為數組的長度。但是此種寫法只能用於聲明時的初始化,不能用於先聲明後賦值的情況,例如,下面的代碼會有編譯錯誤:
int [ ] arr;
arr = { 10,23,30,-10,21 } ;
對於已聲明的數組,可以通過下面的方式對數組類型變量進行初始化:
int[] arr;
arr = new int[]{ 10,23,30,-10,21 };
注意:new之後的[]中不可以寫長度,而元素的個數就是數組的長度。
數組的訪問
獲取數組的長度:
在程序中,調用數組的length屬性可以獲取數組的長度,如下代碼所示:
int[] arr = new int[]{ 3,6,8,9 };
int len = arr . length ;
System.out.println(“數組長度為:” + len);
上面的代碼中,len即為數組的長度,輸出結果為:“數組長度為:4”。
通過下標訪問數組元素:
若想訪問數組中的元素,需要通過下標的方式,需要注意的是,數組的下標從0開始,
最大到length-1,代碼如下所示:
int[ ] arr = new int[]{ 4,5,6,8};
int temp = arr [ 2 ]; //獲取第3個元素,即為6
//交換數組下標為2和3的兩個相鄰元素的值,交互後的結果為:4,5,8,6
int temp = arr [ 2 ] ;
arr [ 2 ] = arr [ 3 ] ;
arr [ 3 ] = temp ;
遍歷數組元素:
在實際的應用中,常常需要對數組整體進行操作,最常見的方式即為遍歷數組元素,通常可選擇for循環語句,循環變量作為訪問數組元素的下標,即可訪問數組中的每一個元素,下面的代碼使用循環方式將數組的每一個元素賦值為100。
int[] arr = new int[10];
for ( int i = 0 ; i < arr.length ; i ++ ){
arr [ i ] = 100;
}
注意:循環的計數器的變化範圍從0到數組長度– 1,可通過寫成“小於長度”這樣的條件來防止下標越界(超出範圍)。
上面的代碼為循環對數組元素賦值,下面兩段代碼為使用循環方式分別正序、逆序輸出數組元素數據:
int [ ] arr = new int [ 5 ] {10,20,30,40,50 } ; //正序輸出
for ( int i=0; i< arr.length; i++) {
System.out.println ( arr[ i ] ) ;
}
int [ ] arr = new int [ 5 ] {10,20,30,40,50 } ; //逆序輸出
for ( int i = (arr.length -1) ; i >= 0 ; i - - ) {
System.out.println ( arr[ i ] ) ;
}
數組的複製:
System.arraycopy方法用於數組複製
public static void arraycopy(Objectsrc, int srcPos,Objectdest, int destPos, int length)
如上代碼的,每一個參數的意義見下列表:
src:源數組
srcPos:源數組中的起始位置
dest:目標數組
destPos : 目標數組中的起始位置
length:要複製的數組元素的數量
通過下面的代碼,可實現數組的複製:
int[ ] a = { 10 ,20 ,30 ,40 ,50 };
int[ ] a1 = new int[ 6 ] ;
System.arraycopy( a , 1 , a1 , 0 , 4 ); 結果:20,30,40,50
如上方法的意義可以理解為:將a數組的從下標1開始的4個元素複製到a1數組中,a1數組從下標0位置開始賦值。程序執行完後,a1的值為20,30,40,50,0,0。其交互效果如圖 – 3所示:
Arrays.copyOf方法用於數組複製:
使用java.util.Arrays類的copyOf方法可實現數組的複製,其結構如下所示:
類型[ ] newArray = Arrays.copyOf ( 類型[ ] original , int newLength )
Arrays.copyOf()方法示例代碼如下所示:
int [ ] a = { 10,20,30,40,50 } ;
int [ ] a1 = Arrays . copyOf ( a, 6 );
上段代碼執行後,a1的結果為:10 20 30 40 50 0,分析其執行過程為:聲明一個整型數組,數組變量名稱為a,賦初始值為10 20 30 40 50,聲明整型數組a1,將a數組數據複製到a1數組,設置其為6個長度,因a數組只有5個元素,所以最後一位補0。故而輸出結果為10 20 30 40 50 0。總結出Arrays.copyOf()方法的特點如下列表所示:
生成的新數組是原始數組的副本;
newLength小於源數組,則進行截取;(自己通過代碼演示效果);
newLength大於源數組,則用0或 null進行填充;
數組的“擴容”
Java語法規定,數組的長度在創建後是不可改變的,這點需要明確。而所謂的擴容實際上是指創建一個更大的新數組並將原有數組的內容複製到其中。可以通過Arrays.copyOf()方法,簡便的實現數組的擴展,代碼如下:
int [ ] a = { 10,20,30,40,50 } ;
a = Arrays . copyOf ( a, a.length+1 );
上段代碼執行後,輸出a數組的數據為:10,20,30,40,50,0。此時a數組的長度為6,實現了所謂的“擴容”。
數組排序:
對數組所施加的算法有很多,其中最常用的即為排序算法。所謂排序,是指將數組元素按照從小到大或從大到小的順序重新排列,當數組元素數較多時, 排序算法的優劣至關重要,因為它將直接影響程序的執行效率,一般情況下,通過排序過程中數組元素的交換次數來衡量排序算法的優劣。
常用排序算法有:插入排序、冒泡排序、快速排序等。今天介紹的是冒泡排序。
冒泡排序是一個非常經典的排序算法,它的排序原則為:比較相鄰的元素,如果違反最後的順序準則(從大到小或是從小到大),則交換。可以簡化理解為:第一次找到所有元素中最大(或最小)的放在最後一個位置上,不再變動;第二次找到剩餘所有元素中最大(或最小)的放在倒數第二個位置上,不再變動,以此類推,直到排序完成。在進行比較時既可以採用“下沉”的方式,也可以使用“上浮”的方式實現。
冒泡排序邏輯如下圖– 1所示。
下面對如上示例進行詳細分析,需求:初始序列為89,50,84,57,61,20,86,升序排(小的在前,大的在後);
第一輪第一次,89與50對比,交換位置,結果:50,89,84,57,61,20,86
第一輪第二次,89與84對比,交換位置,結果:50,84,89,57,61,20,86
第一輪第三次,89與57對比,交換位置,結果:50,84,57,89,61,20,86
第一輪第四次,89與61對比,交換位置,結果:50,84,57,61,89,20,86
第一輪第五次,89與20對比,交換位置,結果:50,84,57,61,20,89,86
第一輪第六次,89與86對比,交換位置,結果:50,84,57,61,20,86,89
將89冒出來了,現在序列為:50,84,57,61,20,86,89
第二輪第一次,50與84對比,位置不換
第二輪第二次,84與57對比,交換位置,結果:50,57,84,61,20,86,89
第二輪第三次,84與61對比,交換位置,結果:50,57,61,84,20,86,89
第二輪第四次,84與20對比,交換位置,結果:50,57,61,20,84,86,89
第二輪第五次,84與86對比,位置不換
將86冒出來了,現在序列為:50,57,61,20,84,86,89
第三輪第一次,50與57對比,位置不換
第三輪第二次,57與61對比,位置不換
第三輪第三次,61與20對比,交換位置,結果:50,57,20,61,84,86,89
第三輪第四次,61與84對比,位置不換
將84冒出來了,現在序列為:50,57,20,61,84,86,89
第四輪第一次,50與57對比,位置不換
第四輪第二次,57與20對比,交換位置,結果:50,20,57,61,84,86,89
第四輪第三次,57與61對比,位置不換
將61冒出來了,現在序列為:50,20,57,61,84,86,89
第五輪第一次,50與20對比,交換位置,結果:20,50,57,61,84,86,89
第五輪第二次,50與57對比,位置不換
將57冒出來了,現在序列為:20,50,57,61,84,86,89
第六輪第一次,20與50對比,位置不換
將50冒出來了,現在的序列為:20,50,57,61,84,86,89
通過上面的分析總結出如下幾點,找出規律,通過程序即可完成冒泡算法的實現。
若數組元素數為7, 則排序過程需要經歷6輪,因為有1個元素是不需要比較的。
若數組元素數為7,第1輪比較6次,第2輪比較5次,依次類推,第6輪只比較1次。
通過如上的分析,寫出冒泡排序算法如下所示:
int[] arr = {89,50,84,57,61,20,86};
for(int i=0;i<arr.length-1;i++){
for(int j=0;j<arr.length-1-i;j++){
if(arr[j]>arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
Arrays.sort方法用於數組排序:
JDK提供的Arrays.sort()方法封裝了數組的排序算法,如下述代碼所示:
int[ ] arr = { 49, 81, 1, 64, 77, 50, 0, 54, 77, 18 };
Arrays.sort( arr ) ;
for(int i=0; i<arr.length; i++) {
System.out.println(arr[i] );
}
分析上面的代碼,輸出結果為:0 1 18 49 50 54 64 77 77 81。可以看到,藉助於Arrays.sort()方法實現了升序排列。