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

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

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

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

4、判斷練習(xí)l 編寫(xiě)程序：從鍵盤(pán)上讀入一個(gè)學(xué)生成績(jī)，存放在變量score中，根據(jù)score的值輸出其對(duì)應(yīng)的成績(jī)等級(jí)：score=90 等級(jí)：A70=score90 等級(jí): B60=score70 等級(jí): 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)語(yǔ)句功能循環(huán)語(yǔ)句功能在某些條件滿(mǎn)足的情況下，反復(fù)執(zhí)行特定代碼的功能l 循環(huán)語(yǔ)句的四個(gè)組成部分循環(huán)語(yǔ)句的四個(gè)組成部分初始化部分（init_statement）循環(huán)條件部分（test_exp） 循環(huán)體部分（body_statement） 迭代部分（alter_statement） l 循環(huán)語(yǔ)句分類(lèi)循環(huán)語(yǔ)句分類(lèi)for 循環(huán)while 循環(huán)do/while 循環(huán) for 循環(huán)語(yǔ)句循環(huán)語(yǔ)句l 語(yǔ)法格式語(yǔ)法格式 for (初始化表達(dá)式初始化表達(dá)式; 布爾值測(cè)試

6、表達(dá)式布爾值測(cè)試表達(dá)式; 更改表達(dá)式更改表達(dá)式) 語(yǔ)句或語(yǔ)句塊語(yǔ)句或語(yǔ)句塊 ； 1234while 循環(huán)語(yǔ)句循環(huán)語(yǔ)句l 語(yǔ)法格式語(yǔ)法格式 初始化語(yǔ)句初始化語(yǔ)句while( 布爾值測(cè)試表達(dá)式布爾值測(cè)試表達(dá)式) 語(yǔ)句或語(yǔ)句塊語(yǔ)句或語(yǔ)句塊;更改語(yǔ)句更改語(yǔ)句;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)語(yǔ)句

7、循環(huán)語(yǔ)句l 語(yǔ)法格式語(yǔ)法格式初始化語(yǔ)句初始化語(yǔ)句do 語(yǔ)句或語(yǔ)句塊語(yǔ)句或語(yǔ)句塊; 更改語(yǔ)句更改語(yǔ)句;while(布爾值測(cè)試表達(dá)式布爾值測(cè)試表達(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 每個(gè)數(shù)組都有一個(gè)屬性length指明它的長(zhǎng)度，例如：a.length 指明數(shù)組a的長(zhǎng)度(元素個(gè)數(shù))數(shù)組一旦初始化，其長(zhǎng)度是不可變的 經(jīng)

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

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

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; 定義一個(gè)名稱(chēng)為arr的二維數(shù)組，二維數(shù)組中有三個(gè)一維數(shù)組 每一個(gè)一維數(shù)組中具體元素也都已初始化 第一個(gè)一維數(shù)組 arr0 = 3,8,2; 第二個(gè)一維數(shù)組 arr1 = 2,7; 第三個(gè)一維數(shù)組 arr2 = 9,0,1,6; 第三個(gè)一維數(shù)組的長(zhǎng)度表示方式：arr2.length; 注意特殊寫(xiě)法情況：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ù)組打印一個(gè) 10 行楊輝三角.11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 1 . 【提示】 1. 第一行有 1 個(gè)元素, 第 n 行有 n 個(gè)元素 2. 每一行的第一個(gè)元素和最后一個(gè)元素都是 1 3. 從第三行開(kāi)始, 對(duì)于非第一個(gè)元素和最后一個(gè)元素的元素. yangh

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

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

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

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