Java 語言基礎 Day05
====================

Core Java

Think in Java Java編程思想

常見排序算法, 學習for循環if語句, 數組操作
選擇排序
冒泡排序
插入排序

Java API 提供的排序算法使用
簡單遞歸調用

1. 3.
練習使用for循環和
數組, 有些面試題中會出現.在實際工程項目中有現成的優化的排序API
1) 選擇排序
原理:a 將數組中的每個元素,與第壹個元素比較
如果這個元素小于第壹個元素, 就將這個
兩個元素交換.
b 每輪使用a的規則, 可以選擇出壹個最小元素
放到第壹個位置.
c 經過n-1輪比較完成排序
簡單說: 每輪選擇最小的放到前面.
原理說明:
ary={8,2,3,7,1}
ary={1|8,3,7,2}
ary={1,2|8,7,3}
ary={1,2,3|8,7}
ary={1,2,3,7|8}
代碼分析:
i 代表第壹個數據的位置
j 代表後部每壹個數據的位置
ary i j ary[i] ary[j] ary[i]>ary[j] [i]<->[j]
{8|2,3,7,1} 0 1 8 2 true 8<->2
{2|8,3,7,1} 0 2 2 3 false
{2|8,3,7,1} 0 3 2 7 false
{2|8,3,7,1} 0 4 2 1 true 2<->1
{1,8|3,7,2} 1 2 8 3 true 8<->3
{1,3|8,7,2} 1 3 3 7 false
{1,3|8,7,2} 1 4 3 2 true 3<->2
{1,2,8|7,3} 2 3 8 7 true 8<->7
{1,2,7|8,3} 2 4 7 3 true 7<->3
{1,2,3,8|7} 3 4 8 7 true 8<->7
{1,2,3,7,8}
i= 0 ~ < ary.length - 1; j=i+1 ~ ary[j]){
int t=ary[i]; ary[i]=ary[j]; ary[j]=t;
}

2) 冒泡排序
原理: a 逐壹比較數組中相鄰的兩個元素, 如果後面
的數字小于前面的數字, 就交換先後元素.
b 經過壹個輪次的比較, 壹定有壹個最大的排
在最後的位置.
c 每次比較剩下的元素, 經過n-1次比較, 可以
實現排序
簡單說: 比較相鄰元素,大的向後交換
原理說明:
ary={8,2,3,7,1}
ary={2,8,3,7,1}
ary={2,3,8,7,1}
ary={2,3,7,8,1}
ary={2,3,7,1|8}
ary={2,3,7,1|8}
ary={2,3,7,1|8}
ary={2,3,1|7,8}
ary={2,3,1|7,8}
ary={2,1|3,7,8}
ary={1,2,3,7,8}
i代表次數
j代表比較位置
ary i j j+1 ary[j] ary[j+1] [j]>[j+1] [j]<->[j+1]
{8,2,3,7,1} 0 0 1 8 2 true 8<->2
{2,8,3,7,1} 0 1 2 8 3 true 8<->3
{2,3,8,7,1} 0 2 3 8 7 true 8<->7
{2,3,7,8,1} 0 3 4 8 1 true 8<->1
{2,3,7,1|8} 1 0 1 2 3 false
{2,3,7,1|8} 1 1 2 3 7 false
{2,3,7,1|8} 1 2 3 7 1 true 7<->1
{2,3,1|7,8} 2 0 1 2 3 false
{2,3,1|7,8} 2 1 2 3 1 true 3<->1
{2,1|3,7,8} 3 0 1 2 1 true 2<->1
{1,2,3,7,8}
i = 0~ < ary.length-1 j = 0~ < ary.length - i -1; if([j]>[j+1]){
[j]<->[j+1]
}

3) 插入排序
原理: a 將數組分爲兩部分, 將後部分的第壹張逐壹
與前部分每壹張比較, 如果當前元素小, 就
壹點被比較元素.
b 找到合理位置插入.
原理說明:
temp = 1
{8|2,3,7,1}
{2,8|8,7,1}
{2,3,8|7,1}
{2,3,8|8,1}
{2,3,7,8|8}
{2,3,7,7|8}
{2,3,3,7|8}
{2,2,3,7|8}
{1,2,3,7|8}

temp 代表取出的待插入元素
i 代表後組待插入元素 位置
j 代表前組每個元素的位置
(移動) 插入
ary i t j ary[j] t<[j] [j]->[j+1] t->[j+1]
{8|2,3,7,5} 1 2 0 8 true 8->[j+1]
{8|8,3,7,5} 1 2 -1 2->[j+1]
{2,8|3,7,5} 2 3 1 8 true 8->[j+1]
{2,8|8,7,5} 2 3 0 2 false 3->[j+1]
{2,3,8|7,5} 3 7 2 8 true 8->[j+1]
{2,3,8|8,5} 3 7 1 3 false 7->[j+1]
{2,3,7,8|5} 4 5 3 8 true 8->[j+1]
{2,3,7,8|8} 4 5 2 7 true 7->[j+1]
{2,3,7,7|8} 4 5 1 3 false 5->[j+1]
{2,3,5,7|8} 5

i= 1 ~ =0 && [j]>t, j–
[j]->[j+1] //移動
t->[j+1]//插入

2. java 系統排序 Arrays.sort(), 排序算法性能很好

3. 方法的遞歸調用
1) java 的棧: 是Java進程啓動時候在內存中開辟的存儲空間
棧內存的利用方式LIFO(後進先出). Java所有局部變量都在棧中
分配(壓入), 方法的參數也是局部變量, 局部變量在離開作用域
時候回收 就是從棧中彈出(刪除).
2) Java方法調用使用棧實現, 遞歸調用就是棧實現的
3) 遞歸時候要按照遞歸深度分配全部臨時變量, 棧開銷很大, 性能
不好, 要注意不要超過棧的大小, 並且壹定要給出結束條件, 否則
會造成棧溢出錯誤.

案例：1+2+3+…+n=f(n)=n+f(n-1) && (n>0, f(1)=1)
注意事項: 解決問題簡練，性能很差。壹定給出結束條件。

作業：
1 複習並且實現全部案例，找出全部的疑問，並解決。
2 實現遞歸代碼：
//案例：n!=1*2*3*…*n=f(n)
// =n*f(n-1) && f(1)=1;

//案例：1+3+5+…+n=f(n)
// =n+f(n-1) && f(1)=1;

//案例：1/1+1/2+1/3+…+1/n=f(n)
// =1/n+f(n-1) && f(1)=1;

3 案例

實現隨機生成雙色球號碼: [02 22 13 16 18 12] [12]
紅球 33 個球 (01~33) 取 六
藍球 16 個球 (01~16) 取 壹

提示:
藍球池 {“01”, “02”, “03”, “04”, … “16”}
紅球池 {“01”, “02”, “03”, “04”, … “33”}
使用標記{ f, f, f, f, … f}

結果采用壹個數組存儲, 數組可以利用數組擴容追加新的”球號”
處理邏輯參考如下過程:

1 隨機生成紅球序號
2 檢查”紅球序號”是否使用過(取出過)
如果使用過 返回 1
3 取出壹個紅球, 設置使用標記爲true
4 是否取出了6個紅球
如果沒有到6個, 返回 1
5 對紅球結果排序
6 取出壹個籃球到結果中

4 案例: 生成4位網站驗證碼,
1 不能重複
2 數字和大小寫字符, 但是不能包含1,0,o,O,l,L,Z,2,9,g等

案例4: (選做) 將壹個整數數位翻轉
如: 整數 56123
返回結果爲整數: 32165
提示: 使用 %10 獲取最後壹位
使用 /10 去除處理完的最後壹位

num sum n=num%10 sum*10+n -> sum num/10 -> num
56123 0 3 3 5612
5612 3 2 32 561
561 32 1 321 56
56 321 6 3216 5
5 3216 5 32165 0
0 32165

Code Package

课堂提纲教案