《Java 程序設(shè)計基礎(chǔ)》 課件 第四章-方法與數(shù)組

Java程序設(shè)計基礎(chǔ)方法與數(shù)組方法與數(shù)組主要內(nèi)容14.1Java方法（重點）4.2一維數(shù)組（重點）4.3簡單的排序算法（重點、難點）4.4二維數(shù)組本章教學(xué)目標(biāo)2能理解int型數(shù)組的內(nèi)存演變過程能理解String型數(shù)組的內(nèi)存演變過程能準(zhǔn)確的使用遞歸方法解決常見問題能理解冒泡排序、插入排序和快速排序的算法邏輯能準(zhǔn)確的編寫冒泡排序、插入排序和快速排序的實現(xiàn)代碼能區(qū)分單向掃描法和雙向掃描法兩種方式的快速排序能理解二維數(shù)組的存儲結(jié)構(gòu)能理解二維數(shù)組的存儲結(jié)構(gòu)能準(zhǔn)確的為二維數(shù)組元素賦值、遍歷二維數(shù)組元素能理解int型數(shù)組的內(nèi)存演變過程能理解String型數(shù)組的內(nèi)存演變過程能準(zhǔn)確的使用遞歸方法解決常見問題能理解冒泡排序、插入排序和快速排序的算法邏輯能準(zhǔn)確的編寫冒泡排序、插入排序和快速排序的實現(xiàn)代碼能區(qū)分單向掃描法和雙向掃描法兩種方式的快速排序能準(zhǔn)確的為二維數(shù)組元素賦值、遍歷二維數(shù)組元素什么是Java方法3方法是Java中一個命名的代碼塊，我們一直在使用的main就是一個方法方法可以提高代碼的復(fù)用度，減少重復(fù)方法可以使程序結(jié)構(gòu)更加清晰Java方法聲明的語法形式如下（重點）

[修飾符]返回值類型方法名([形參列表]){方法體}大括號前面的內(nèi)容稱為方法頭，大括號中的內(nèi)容稱為方法體方法聲明后如何調(diào)用4本節(jié)介紹類內(nèi)部方法的調(diào)用在類內(nèi)部調(diào)用方法，只需給出方法名以及方法的實際參數(shù)列表（實參列表的數(shù)據(jù)類型必須與形參列表一致或可以自動轉(zhuǎn)換成形參列表的格式），如下intx=returnAdd(3+5);drawStar(8);使用方法調(diào)用的形式，代碼結(jié)構(gòu)清晰，方法聲明可以被復(fù)用JDK本身也提供了很多的方法，我們也一直都在使用。例如，System.out.println()就是在調(diào)用JDK提供的方法向向控制臺輸出，nextInt()方法（Scanner類）從控制臺獲取用戶輸入的整數(shù)等方法聲明里的元素:修飾符和返回值類型5修飾符：用來規(guī)定方法的可見范圍等特征例如，我們一直在使用的main方法，其中的publicstatic就是修飾符，public表示這個方法的可見范圍，static表示main方法是一個靜態(tài)方法返回值類型：表示該方法返回什么類型的值特殊的，如果方法無需返回值，這時需要用void表示一旦一個方法需要返回值時，那么方法體中就必須使用return語句返回此類型的值方法聲明里的元素:修飾符和返回值類型6示例publicvoiddrawCircular()//該方法的返回值為空{(diào)...}publicintreturnInt(){//該方法返回值為int類型

intx=10;

...

returnx;}一個方法只能有一個返回值，因此也只能有一個返回值類型如果邏輯上確實需要返回多個值，則可以將需要返回的“多個值”先轉(zhuǎn)換為一個數(shù)組或一個對象，然后再返回轉(zhuǎn)換后的這“一個值”方法聲明里的元素:方法名和形參列表7示例publicintreturnAdd(intx,inty){//x、y是形參returnx+y;}//以下是方法調(diào)用，后續(xù)講解；這里僅用于區(qū)分形參和實參publicinttest(){

returnAdd(1,2);

//1、2是實參}一個特殊的方法(遞歸)8遞歸調(diào)用是指一個方法在它的方法體內(nèi)調(diào)用它自身Java語言允許方法的遞歸調(diào)用，在遞歸調(diào)用中，主調(diào)方法同時也是被調(diào)方法。執(zhí)行遞歸方法將反復(fù)調(diào)用其自身，每調(diào)用一次就再進(jìn)入一次本方法遞歸調(diào)用最容易出現(xiàn)的問題是，如果遞歸調(diào)用沒有退出的條件，則遞歸方法將無休止地調(diào)用其自身，這顯然是不正確的。為了防止遞歸調(diào)用無休止地進(jìn)行，必須在方法內(nèi)有終止遞歸調(diào)用的手段。通常的做法就是增加條件判斷，滿足某條件后就不再進(jìn)行遞歸調(diào)用，然后逐層返回一個特殊的方法(遞歸)9示例：使用遞歸調(diào)用計算整數(shù)n的階乘//求n的階乘的方法longfactorial(intn){if(n==1){//判斷條件，一旦滿足就不再遞歸，逐層返回return1;}longsum=factorial(n-1);//遞歸調(diào)用returnsum*n;//逐層返回求階乘}什么是數(shù)組10如果一個系統(tǒng)中存儲的是一個Java工程師信息，假設(shè)這個系統(tǒng)需要存儲100個Java工程師信息，如何便捷的存儲這些信息？使用數(shù)組Java提供了一種稱為數(shù)組的數(shù)據(jù)類型，數(shù)組不是基本數(shù)據(jù)類型，而是引用數(shù)據(jù)類型數(shù)組是把相同類型的多個變量按一定順序組織起來，這些按序排列的同類型數(shù)據(jù)元素的集合稱為數(shù)組數(shù)組中的元素在內(nèi)存中是連續(xù)存儲的數(shù)組中的數(shù)據(jù)元素既可以是基本類型，也可以是引用類型使用數(shù)組的三個步驟(聲明、創(chuàng)建和賦值)11使用數(shù)組時，需要聲明、創(chuàng)建、賦值并使用三個步驟聲明數(shù)組的語法形式如下，推薦使用前一種

數(shù)據(jù)類型[]數(shù)組名;或數(shù)據(jù)類型數(shù)組名[];聲明數(shù)組就是告訴內(nèi)存，該數(shù)組中元素是什么類型的，如下intengNo[];double[]engSalary;String[]engName;//String字符串是引用類型，engName數(shù)組里存放的是引用類型元素必須注意，Java語言中聲明數(shù)組的時候不可以指定數(shù)組長度，例如intengNo[100]是非法的使用數(shù)組的三個步驟(聲明、創(chuàng)建和賦值)12創(chuàng)建數(shù)組，就是要為數(shù)組分配內(nèi)存空間，不分配內(nèi)存是不能存放數(shù)組元素的，創(chuàng)建數(shù)組就是在內(nèi)存中劃分出幾個連續(xù)的空間用于依次存儲數(shù)組中的數(shù)據(jù)元素，其語法形式如下

數(shù)組名=new數(shù)據(jù)類型[數(shù)組長度];也可以把數(shù)組聲明和數(shù)組創(chuàng)建合并，其語法形式為：

數(shù)據(jù)類型[]數(shù)組名=new數(shù)據(jù)類型[數(shù)組長度];其中數(shù)組長度就是數(shù)組中存放的元素個數(shù)，必須是正整數(shù)，如下int[]engNo=newint[5];String[]engName=newString[5];使用數(shù)組的三個步驟(聲明、創(chuàng)建和賦值)13賦值并使用數(shù)組。在使用數(shù)組時，主要通過下標(biāo)來訪問數(shù)組元素給數(shù)組賦值的語法形式如下

數(shù)組名[數(shù)組下標(biāo)]=數(shù)值;數(shù)組下標(biāo)從0開始編號，數(shù)組名[0]代表數(shù)組中第1個元素，數(shù)組名[1]代表數(shù)組中第2個元素...數(shù)組下標(biāo)的最大值為數(shù)組長度減1，如果下標(biāo)值超過最大值會出現(xiàn)數(shù)組下標(biāo)越界問題，如下engNo[0]=1001;engNo[1]=1002;`engName[4]="張三";engName[5]="李四";//錯誤，數(shù)組的最大長度是5，因此最后一個數(shù)組元素是engName[4]一維數(shù)組的靜態(tài)初始化14本節(jié)介紹一維數(shù)組的靜態(tài)初始化，即在聲明、創(chuàng)建的時候同時直接為元素賦值int[]engNo=newint[]{1001,1002,1003,1004,1005};String[]engName=newString[]{"柳海龍","孫傳杰","孫悅"};甚至可以直接寫成：int[]engNo={1001,1002,1003,1004,1005};String[]engName={"柳海龍","孫傳杰","孫悅"};靜態(tài)初始化適用于一開始就知道數(shù)組內(nèi)容的情況數(shù)組的內(nèi)存結(jié)構(gòu)15數(shù)組不屬于基本數(shù)據(jù)類型（雖然其內(nèi)部存儲的可能是基本數(shù)據(jù)類型），只能是引用數(shù)據(jù)類型。因此語句int[]engNo=newint[]{1001,1002,1003,1004,1005};中，數(shù)組本身是在堆內(nèi)存中開辟的空間，該空間的地址存儲在棧內(nèi)存中并命名為engNo，如圖int型數(shù)組的內(nèi)存演變過程16聲明，int[]engNo;在棧內(nèi)存中分配1個空間命名為engNo，用于存放整型數(shù)組的地址（現(xiàn)在這個地址還不存在，默認(rèn)是null）創(chuàng)建，int[]engNo=newint[5];在堆內(nèi)存中分配5個連續(xù)空間，并把空間地址賦給engNo，使engNo指向這5個連續(xù)的內(nèi)存空間，這5個空間里存放的默認(rèn)初始值為0（整數(shù)的默認(rèn)值），如圖所示int型數(shù)組的內(nèi)存演變過程17賦值，engNo[0]=1001;將整數(shù)1001放到engNo數(shù)組的第1個元素空間里，如圖所示int型數(shù)組的內(nèi)存演變過程18賦值，engNo[1]=1002;將整數(shù)1002放到engNo數(shù)組的第2個元素空間里，如圖所示String型數(shù)組的內(nèi)存演變過程19引用的名稱實際代表的是存放數(shù)據(jù)的地址。因此，如果數(shù)組中的元素是String類型，那么數(shù)組元素存放的就是String類型的引用即數(shù)據(jù)的地址。在使用String[]names=newString[4];創(chuàng)建字符串?dāng)?shù)組時，會在堆內(nèi)存中分配4個連續(xù)空間，并把空間地址賦給names，使names指向這4個連續(xù)的內(nèi)存空間。這4個空間里存放的默認(rèn)初始值為null（String類型數(shù)據(jù)的默認(rèn)值），如圖所示。String型數(shù)組的內(nèi)存演變過程20names[0]="王云";因為數(shù)組的元素是引用類型，因此會將"王云"的地址放到names數(shù)組的第1個元素空間里之后，依次將"劉靜濤","南天華","雷靜"的地址存放到names中相應(yīng)的位置，如圖所示為什么要學(xué)習(xí)排序算法21從實際編程的角度看，使用Java的一些工具類中的排序方法，就可以實現(xiàn)排序的功能。但作為學(xué)習(xí)數(shù)組的強(qiáng)化，編寫一些簡單算法是很有益處的所謂排序，就是使一串記錄（通常存儲在數(shù)組中），按照某種算法，遞增或遞減地排列起來的操作排序的算法有很多，各種算法對空間的要求及時間效率也各有差別冒泡排序22通過上面的分析可以看出，假設(shè)需要排序的序列的個數(shù)是n，則需要經(jīng)過n-1輪，最終完成排序。在第一輪中，比較的次數(shù)是n-1次，之后每輪減少1次。插入排序23插入排序?qū)⒋判虻臄?shù)據(jù)分為兩個部分，第一部分中的數(shù)據(jù)是已經(jīng)排好序的（初始時，第一個數(shù)據(jù)劃入第一部分），第二部分中的數(shù)據(jù)是無序的。之后，每次從第二部分取出頭部（即第一個）元素，把它插入到第一部分的合適位置，使插入后的第一部分仍然有序。直接插入排序的具體流程如下第一輪：以下標(biāo)1的元素（記為a1，后面類似）為頭部向前找插入位置，如果a1≥a0，則維持現(xiàn)狀；否則a1向前插（a0后移，位置0處將a1放入）。

第二輪：以a2為頭部向前找插入位置，如果a2≥a1，則維持現(xiàn)狀；否則a1向后挪。繼續(xù)與a0比較，此時如果a2≥a0，則在位置1處放入a2，如果a0＞a2，將a0后挪一位，在位置0處將a2放入。

總的來說，第i輪時，ai為待定位的數(shù)據(jù)，通過與前序數(shù)據(jù)比較并將更大的數(shù)據(jù)后挪（如有必要）的方式找到合適的位置插入ai，使得數(shù)組的前i+1個元素有序。一共要進(jìn)行n-1輪?？焖倥判蚍?4快速排序是對冒泡排序的一種改進(jìn)，是通過每一趟排序，將要排序的數(shù)組（或后續(xù)講解的集合）分割成兩個獨立的部分。其中，一部分的所有數(shù)據(jù)比另一部分的所有數(shù)據(jù)都要小。然后通過遞歸重復(fù)這種操作，對分割后的兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，最終達(dá)到整個數(shù)據(jù)都是有序排列的。本節(jié)將會介紹單向掃描法和雙向掃描法兩種方式的快速排序?？焖倥判蚍?5快速排序之單向掃描法選定數(shù)組的一個元素，將之稱為“主元”。之后，掃描一趟數(shù)組，將大于或等于主元的元素放在主元的右邊，把小于或等于主元的元素放在主元的左邊，這個過程被稱為用主元分割數(shù)組。

具體做法是：

1.選定數(shù)組的第一個元素（即nums數(shù)組中的元素4）作為主元。

2.定義兩個標(biāo)記變量sp和bigger，它們都是數(shù)組下標(biāo)。其中sp表示1中，在從左往右掃描一趟數(shù)組的過程中，當(dāng)前正在掃描的位置，它會向右移動；bigger是邊界，其右側(cè)的數(shù)據(jù)大于或等于主元。初始時，sp指向數(shù)組的第二個元素，bigger指向數(shù)組的最后一個元素，如圖所示快速排序法26

3.假設(shè)數(shù)組名是arr，第一趟的比較流程是：在sp≤bigger的情況下循環(huán)，比較arr[sp]<=主元是否成立，如果是，sp右移一位；否則，就交換arr[sp]和arr[bigger]，并將bigger的位置左移一位（注意sp原地不動），第一次比較過程如圖所示。

（1）數(shù)據(jù)交換前快速排序法27

（2）數(shù)據(jù)交換后（3）bigger左移一位快速排序法28

4.繼續(xù)循環(huán)，重復(fù)c中描述的過程，如下。

（1）（續(xù)接上圖)因為當(dāng)前的arr[sp]<=主元（1<4）成立，所以sp右移一位即sp++；

（2）此時arr[sp]<=主元（6>4）不成立，所以交換arr[sp]和arr[bigger]，再將bigger左移一位，如下圖所示。數(shù)據(jù)交換前快速排序法29數(shù)據(jù)交換后bigger左移一位快速排序法30

（1）因為arr[sp]<=主元（2<4）成立，sp右移一位，如圖所示

sp右移一位

（2）因為arr[sp]<=主元（7>4）不成立，所以交換arr[sp]和arr[bigger]，再將bigger左移一位，如下圖所示數(shù)據(jù)交換前快速排序法31數(shù)據(jù)交換后bigger左移一位快速排序法32

此時，sp==bigger，仍要繼續(xù)判斷，此處因為arr[sp]<=主元（3<4）成立，所以sp還會右移一次變?yōu)榇笥赽igger，而bigger保持不動至此，循環(huán)結(jié)束，bigger右側(cè)的數(shù)據(jù)全部大于或等于主元，注意bigger本身指向的數(shù)據(jù)是小于主元的，下面通過交換arr[bigger]和主元就可以完成以主元分割數(shù)組的任務(wù)

快速排序法335.交換arr[bigger]和主元，如圖所示。此時，主元左邊的元素都小于主元，主元右邊的元素都大于或等于主元。即主元已經(jīng)是處在排好序的位置了。將此時的數(shù)組以主元為界，分割為兩部分，分別對兩部分遞歸處理，即從a.開始——選取新的主元（圖中的新主元1和新主元2），如圖所示。用同樣的方法，將新的主元也放置到排好序的位置快速排序法34遞歸的結(jié)束條件是：子數(shù)組只有1個元素或者0個元素快速排序法35快速排序之雙向掃描法雙向掃描法仍然是選取第一個元素為主元，然后在主元以外的元素里，從左右兩側(cè)同時掃描，如下圖中的left、right

快速排序法36left在向右掃描（移動）的過程中，如果arr[left]<=主元成立，則left右移，否則停止移動；right向左掃描的過程中，如果arr[right]>=主元成立，則right左移，否則停止移動。當(dāng)left和right都停止移動時，如果這時left<=right，則交換左右arr[left]和arr[right]，如下圖所示。掃描停止并準(zhǔn)備交換數(shù)據(jù)：

快速排序法37交換后的數(shù)據(jù)：之后繼續(xù)向中間遍歷，直到left>right，如下。1.上一個圖中，arr[left]<=主元成立，所以left右移；arr[right]>=主元成立，所以right左移，如圖所示

快速排序法38此時，left<right，因此需要交換arr[left]和arr[right]，如圖所示。right左移數(shù)據(jù)交換前:right左移數(shù)據(jù)交換后:

快速排序法392.上一個圖中，arr[left]<=主元成立，所以left右移；arr[right]>=主元成立，所以right左移，如圖所示此時，left<=right成立，且left和right滿足停止條件，因此需要交換arr[left]和arr[right]，如下圖所示。數(shù)據(jù)交換前：

快速排序法40數(shù)據(jù)交換后：

快速排序法413.上一個圖中，arr[left]<=主元成立，所以left右移；arr[right]>=主元成立，所以right左移，如圖所示此時,已達(dá)到了循環(huán)退出條件left>right，因此循環(huán)終止

快速排序法424.再交換主元與arry[right]，如下圖所示。主元與arry[right]交換前：主元與arry[right]交換后：

快速排序法43至此，主元也處在了合適的位置上，一趟排序結(jié)束。再用遞歸，將主元左側(cè)和右側(cè)的子數(shù)組視為兩個需要排序的數(shù)組，重復(fù)以上步驟即可實現(xiàn)對整個數(shù)組的排序。

二維數(shù)組44Java語言允許構(gòu)造多維數(shù)組并存儲多維數(shù)據(jù)多維數(shù)組的數(shù)組元素有多個下標(biāo)，以標(biāo)識它在數(shù)組中的位置聲明并創(chuàng)建二維數(shù)組的語法形式如下數(shù)據(jù)類型[][]數(shù)組名;或數(shù)據(jù)類型數(shù)組名[][];數(shù)組名=new數(shù)據(jù)類型[第一維長度][第二維長度];創(chuàng)建的時候，可以同時設(shè)置第一維長度和第二維長度，也可以只設(shè)置第一維長度，但不可以只設(shè)置第二維長度int[][]arr=newint[3][4];int[][]arr=newint[3][];二維數(shù)組45二維數(shù)組本質(zhì)是一維數(shù)組的疊加，二維數(shù)組的所有元素都是引用類型，這些元素分別指向不同的一維數(shù)組，其內(nèi)存結(jié)構(gòu)和之前介紹的一維數(shù)組類似。例如，二維數(shù)組arr指向了由arr[0]、arr[1]和arr[2]組成的數(shù)組，而arr[0]、arr[1]和arr[2]自身也是一維數(shù)組。arr[0]、arr[1]和arr[2]是二維數(shù)組的三個元素，這三個鑰匙盒是并排的。arr[0]、arr[1]和arr[2]所引用的是三個獨立的數(shù)組，由于new操作符總是開辟新的空間且無法保證連續(xù)，arr[0]、arr[1]和arr[2]中的“鑰匙”（即地址）不是連續(xù)的，如圖所示。二維數(shù)組46二維數(shù)組的賦值和使用與一維數(shù)組類似，都是通過下標(biāo)訪問數(shù)組元素，不同的是一維數(shù)組只有一個下標(biāo)，而二維數(shù)組有兩個下標(biāo)，分別表示該元素所在數(shù)組的行數(shù)和列數(shù)。例如arr[0][3]，其表示的是數(shù)組arr中第1行第4列的元素如何遍歷二維數(shù)組？二維數(shù)組是二維的，是由“行”和“列”構(gòu)成的。因此，只