Java中數(shù)組結(jié)構(gòu)及經(jīng)典排序算法解析

1、JavaJava中數(shù)組結(jié)構(gòu)中數(shù)組結(jié)構(gòu)及及經(jīng)典經(jīng)典排序算法解析排序算法解析講師：宋紅康講師：宋紅康 新浪微博：尚硅谷新浪微博：尚硅谷- -宋紅康宋紅康 解析流程控制結(jié)構(gòu)在開發(fā)時具體使用及解析流程控制結(jié)構(gòu)在開發(fā)時具體使用及面試面試陷阱陷阱 解讀常用存儲容器解讀常用存儲容器數(shù)組的內(nèi)存數(shù)組的內(nèi)存結(jié)構(gòu)結(jié)構(gòu) 多種排序算法實現(xiàn)及其復(fù)雜度分析多種排序算法實現(xiàn)及其復(fù)雜度分析l 順序結(jié)構(gòu)順序結(jié)構(gòu) 程序從上到下逐行地執(zhí)行，中間沒有任何判斷和跳轉(zhuǎn)。l 分支分支結(jié)構(gòu)結(jié)構(gòu) 根據(jù)條件，選擇性地執(zhí)行某段代碼。 有ifelse和switchcase兩種分支語句。l 循環(huán)循環(huán)結(jié)構(gòu)結(jié)構(gòu) 根據(jù)循環(huán)條件，重復(fù)性的執(zhí)行某段代碼。 有wh

2、ile、dowhile、for三種循環(huán)語句。 注：JDK1.5提供了foreach循環(huán)，方便的遍歷集合、數(shù)組元素。if語句三語句三種格式種格式：1. if(條件表達(dá)式條件表達(dá)式)執(zhí)行代碼塊；執(zhí)行代碼塊； 2. if(條件表達(dá)式條件表達(dá)式)執(zhí)行代碼塊；執(zhí)行代碼塊； else執(zhí)行代碼塊；執(zhí)行代碼塊； 3. if(條件表達(dá)式條件表達(dá)式)執(zhí)行代碼塊；執(zhí)行代碼塊； else if (條件表達(dá)式條件表達(dá)式)執(zhí)行代碼塊；執(zhí)行代碼塊； else執(zhí)行代碼塊；執(zhí)行代碼塊； 分支語句分支語句1： if-else語句語句分支分支結(jié)構(gòu)結(jié)構(gòu)2：switch語句語句switch(表達(dá)式表達(dá)式)case 常量1:語句1;br

3、eak;case 常量2:語句2;break; case 常量N:語句N;break;default:語句;break; switch語句有關(guān)規(guī)則語句有關(guān)規(guī)則l switch(表達(dá)式)中表達(dá)式的返回值返回值必須是下述幾種類型之一：byte，short，char，int，枚舉，枚舉，String；l case子句中的值必須是常量常量，且所有case子句中的值應(yīng)是不同的；l default子句是可任選的可任選的，當(dāng)沒有匹配的case時，執(zhí)行defaultl break語句用來在執(zhí)行完一個case分支后使程序跳出switch語句塊；如果沒有break，程序會順序執(zhí)行到switch結(jié)尾條件判斷練習(xí)條件

4、判斷練習(xí)l 編寫程序：從鍵盤上讀入一個學(xué)生成績，存放在變量score中，根據(jù)score的值輸出其對應(yīng)的成績等級：score=90 等級：A70=score90 等級: B60=score70 等級: Cscore 2) if (y 2) System.out.println(x + y); System.out.println(atguigu); else System.out.println(x is + x);2)boolean b = true; if(b = false) System.out.println(a); else if(b) System.out.println(b);

5、else if(!b) System.out.println(c); else System.out.println(d);循環(huán)循環(huán)結(jié)構(gòu)結(jié)構(gòu)l 循環(huán)語句功能循環(huán)語句功能在某些條件滿足的情況下，反復(fù)執(zhí)行特定代碼的功能l 循環(huán)語句的四個組成部分循環(huán)語句的四個組成部分初始化部分（init_statement）循環(huán)條件部分（test_exp） 循環(huán)體部分（body_statement） 迭代部分（alter_statement） l 循環(huán)語句分類循環(huán)語句分類for 循環(huán)while 循環(huán)do/while 循環(huán) for 循環(huán)語句循環(huán)語句l 語法格式語法格式 for (初始化表達(dá)式初始化表達(dá)式; 布爾值測試

6、表達(dá)式布爾值測試表達(dá)式; 更改表達(dá)式更改表達(dá)式) 語句或語句塊語句或語句塊 ； 1234while 循環(huán)語句循環(huán)語句l 語法格式語法格式 初始化語句初始化語句while( 布爾值測試表達(dá)式布爾值測試表達(dá)式) 語句或語句塊語句或語句塊;更改語句更改語句;l 應(yīng)用舉例應(yīng)用舉例public class WhileLoop public static void main(String args) int result = 0;int i=1;while(i=100) result += i; i+; System.out.println(result= + result); do-while 循環(huán)語句

7、循環(huán)語句l 語法格式語法格式初始化語句初始化語句do 語句或語句塊語句或語句塊; 更改語句更改語句;while(布爾值測試表達(dá)式布爾值測試表達(dá)式); l 應(yīng)用舉例應(yīng)用舉例public class WhileLoop public static void main(String args) int result = 0, i=1; do result += i; i+; while(in-1；如int a=new int3; 可引用的數(shù)組元素為a0、a1、a2l 每個數(shù)組都有一個屬性length指明它的長度，例如：a.length 指明數(shù)組a的長度(元素個數(shù))數(shù)組一旦初始化，其長度是不可變的 經(jīng)

8、典經(jīng)典題目題目從鍵盤讀入學(xué)生成績，找出最高分，并輸出學(xué)生成績等級。成績=最高分-10 等級為A 成績=最高分-20 等級為B成績=最高分-30 等級為C 其余 等級為D提示：先讀入學(xué)生人數(shù)，根據(jù)人數(shù)創(chuàng)建int數(shù)組，存放學(xué)生成績。經(jīng)典面試題目經(jīng)典面試題目題目題目1：一個數(shù)組，讓數(shù)組的每個元素去除第一個元素，得到的商作為被除數(shù)所在位置的新值。題目題目2：金額轉(zhuǎn)換，阿拉伯?dāng)?shù)字的金額轉(zhuǎn)換成中國傳統(tǒng)的形式。如：105600123 = 壹億零仟伍佰陸拾零萬零仟壹佰貳拾叁圓整題目題目3：創(chuàng)建一個長度為6的int型數(shù)組，要求取值為1-30，同時元素值各不相同 1,30 拓展：34-102;1) (int)(M

9、ath.random()*30) + 1;2) While(true).多維數(shù)組多維數(shù)組二維數(shù)組二維數(shù)組：數(shù)組中的數(shù)組：數(shù)組中的數(shù)組格式格式1（動態(tài)初始化）（動態(tài)初始化）：int arr = new int32; 定義了名稱為arr的二維數(shù)組 二維數(shù)組中有3個一維數(shù)組 每一個一維數(shù)組中有2個元素 一維數(shù)組的名稱分別為arr0, arr1, arr2 給第一個一維數(shù)組1腳標(biāo)位賦值為78寫法是：arr01 = 78;格式格式2（動態(tài)初始化）（動態(tài)初始化）：int arr = new int3; 二維數(shù)組中有3個一維數(shù)組。 每個一維數(shù)組都是默認(rèn)初始化值null (注意：區(qū)別于格式1） 可以對這個三個

10、一維數(shù)組分別進(jìn)行初始化 arr0 = new int3; arr1 = new int1; arr2 = new int2;注：intarr = new int3; /非法非法格式格式3（靜態(tài)初始化）（靜態(tài)初始化）：int arr = new int3,8,2,2,7,9,0,1,6; 定義一個名稱為arr的二維數(shù)組，二維數(shù)組中有三個一維數(shù)組 每一個一維數(shù)組中具體元素也都已初始化 第一個一維數(shù)組 arr0 = 3,8,2; 第二個一維數(shù)組 arr1 = 2,7; 第三個一維數(shù)組 arr2 = 9,0,1,6; 第三個一維數(shù)組的長度表示方式：arr2.length; 注意特殊寫法情況：int x

11、,y; x是一維數(shù)組，y是二維數(shù)組。 Java中多維數(shù)組不必都是規(guī)則矩陣形式int i = new int32;12i0i1i2i01 = 12;int i = new int3;i0 = new int2;i1 = new int3;i2 = new int4;經(jīng)典題目經(jīng)典題目題目題目4：使用二維數(shù)組打印一個 10 行楊輝三角.11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 1 . 【提示】 1. 第一行有 1 個元素, 第 n 行有 n 個元素 2. 每一行的第一個元素和最后一個元素都是 1 3. 從第三行開始, 對于非第一個元素和最后一個元素的元素. yangh

12、uiij = yanghuii-1j-1 + yanghuii-1j;排序：排序：假設(shè)含有n個記錄的序列為R1，R2，.,Rn,其相應(yīng)的關(guān)鍵字序列為K1，K2，.,Kn。將這些記錄重新排序為Ri1,Ri2,.,Rin,使得相應(yīng)的關(guān)鍵字值滿足條Ki1=Ki2=.=Kin,這樣的一種操作稱為排序。 通常來說，排序的目的是快速查找。衡量排序算法的優(yōu)劣：衡量排序算法的優(yōu)劣：1.時間復(fù)雜度：分析關(guān)鍵字的比較次數(shù)和記錄的移動次數(shù)2.空間復(fù)雜度：分析排序算法中需要多少輔助內(nèi)存3.穩(wěn)定性：若兩個記錄A和B的關(guān)鍵字值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。排序算法分類：排序算法分類：內(nèi)

13、部排序內(nèi)部排序和和外部排序外部排序。 內(nèi)部排序：整個排序過程不需要借助于外部存儲器（如磁盤等），所有排序操作都在內(nèi)存中完成。 外部排序：參與排序的數(shù)據(jù)非常多，數(shù)據(jù)量非常大，計算機(jī)無法把整個排序過程放在內(nèi)存中完成，必須借助于外部存儲器（如磁盤）。外部排序最常見的是多路歸并排序?？梢哉J(rèn)為外部排序是由多次內(nèi)部排序組成。常用的內(nèi)部排序常用的內(nèi)部排序l 選擇排序選擇排序 直接選擇排序、堆排序l 交換排序交換排序 冒泡排序、快速排序l 插入插入排序排序 直接插入排序、折半插入排序、Shell排序l 歸并排序歸并排序l 桶式排序桶式排序l 基數(shù)排序基數(shù)排序各種內(nèi)部排序方法性能比較各種內(nèi)部排序方法性能比較1.

14、從平均時間而言從平均時間而言：快速排序最佳。但在最壞情況下時間性能不如堆排序和歸并排序。2.從算法簡單性看從算法簡單性看：由于直接選擇排序、直接插入排序和冒泡排序的算法比較簡單，將其認(rèn)為是簡單算法，都包含在上圖的“簡單排序”中。對于Shell排序、堆排序、快速排序和歸并排序算法，其算法比較復(fù)雜，認(rèn)為是復(fù)雜排序。3.從穩(wěn)定性看從穩(wěn)定性看：直接插入排序、冒泡排序和歸并排序時穩(wěn)定的；而直接選擇排序、快速排序、 Shell排序和堆排序是不穩(wěn)定排序4.從待排序的記錄數(shù)從待排序的記錄數(shù)n的大小看的大小看，n較小時，宜采用簡單排序；而n較大時宜采用改進(jìn)排序。排序方法的選擇排序方法的選擇(1)若n較小(如n5

15、0)，可采用直接插入直接插入或直接選擇排序直接選擇排序。 當(dāng)記錄規(guī)模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數(shù)少于直接插入，應(yīng)選直接選擇排序為宜。(2)若文件初始狀態(tài)基本有序(指正序)，則應(yīng)選用直接直接插插入入、冒泡冒泡或隨機(jī)的快速排序快速排序為宜；(3)若n較大，則應(yīng)采用時間復(fù)雜度為O(nlgn)的排序方法：快速排序快速排序、堆排序堆排序或歸并排序歸并排序。操作數(shù)組的工具類：操作數(shù)組的工具類：Arraysl java.util.Arrays類包含了用來操作數(shù)組（比如排序和搜索）的各種方法。Arrays擁有一組static方法。 equals()：比較兩個array是否相等。array擁有相同元素個數(shù)，且所有對應(yīng)元素兩兩相等。fill()：將值填入array中。 sort()：用來對array進(jìn)行排序。 binarySearch()：在排好序的array中尋找元素。 另：System.arraycopy()：array的復(fù)制