Category Archives: Java

[DataStructure]Insertion Sort(插入排序法)

插入排序法的步驟就是把後面的牌抽到前面適當的位置插入

以{123456,123,12,33,44,55}為例

將123插入到最前面 [123 123456] 12 33 44 55 將12插入到最前面 [12 123 123456] 33 44 55 將33插入到12跟123之間 [12 33 123 123456] 44 55 將44插入到33跟123之間 [12 33 44 123 123456] 55 將55插入到44跟123之間 [12 33 44 55 123 123456]

Java

Continue Reading

[Java]LinkedList

List是以物件加入的順序來排序,如果單純用來讀取,建議使用ArrayList,如果大量做插入、刪除等動作,用LinkedList會比ArrayList好上很多

Continue Reading

[Java]HashSet

HashSet是實作Set介面的物件,Set容器中的物件都是唯一的

HashSet

這段程式會顯示出:李四 王五 張三。 其中張三輸入了兩次,所以第二次輸入張三時,會判定已有這個物件 至於順序不一樣是因為HashSet的順序是利用Hash Table排序過的,所以會與當初輸入時不一樣

如果要讓set順序與輸入時相同,可以使用LinkedHashSet

他的走訪就會跟LinkedList一樣

Continue Reading

[DataStructure]Selection Sort(選擇排序法)

選擇排序法的複雜度為O(n^2),和氣泡排序法是一樣的

他的步驟是將要排序的數字分為未排序已排序兩部份

接著在未排序找出最小值插入已排序的末端

以{123456,123,12,33,44,55}為例

未排序 123456 123 12 33 44 55 找到最小值12,並與第一筆123456交換(12是已排序的數字了) [12] 123 123456 33 44 55 找到最小值33,並與第一筆123交換 [12 33] 123456 123 44 55 找到最小值44,並與第一筆123456交換 [12 33 44] 123 123456 55 找到最小值55,並與第一筆123交換 [12 33 44 55] 123456 123 找到最小值123,並與第一筆123456交換 [12 33 44 55 123] 123456 完成 [12 33 44 55 123 123456]

Java

Continue Reading

[DataStructure]Bubble Sort(氣泡排序法)

這是資料結構第一個學到的排序法,

雖簡單但因為複雜度太高效率非常不好(Ο(n^2)),通常實作中都不採用這種排序法

不過對於初學者學習排序的概念非常有幫助

氣泡排序法的概念很容易,分為幾個步驟

1.比較相鄰的元素。如果第一個比第二個大,就交換。 2.對每一對相鄰元素作同樣的工作,從開始第一對到結尾的最後一對(這時候最後一個數應該會是最大) 3.重複以上動作(不包含最後一個數)

Java:

Continue Reading

[DataStructure]Quick Sort(快速排序法)

目前公認最快的排序法,雖然最壞的時候還是會衝到O(n^2),不過大部份還是很快的(Quick Sort的速度與基準點的選擇有關)

Quick Sort分為幾個步驟 以{41,24,76,11,45,64,21,69,19,36}這個陣列為例

1.先將最左邊的數41當成基準點(s) 2.索引 I 由左邊向右找,一直找到大於基準點(s)的數 3.索引 J 由右邊向左找,一直找到小於基準點(s)的數 4.如果 I >= J 就跳出迴圈。如果 I < J,array[I]和array[J]交換 6.基準點與array[J]交換,這時 J 因為第3步驟的關係,會一直找到小於基準點的數(這時 I 已 >= J,雖迴圈跳出了,但 J 的值還在) 7.對基準點左邊及右邊進行相同步驟的遞迴

I 找到比基準點大的、J 找到比基準點小的 [41],24,76(I),11,45,64,21,69,19,36(J) I、J交換,繼續往下找 [41],24,36,11,45(I),64,21,69,19(J),76 I、J交換,繼續往下找 [41],24,36,11,19,64(I),21(J),69,45,76 I、J交換且繼續往下找,但是 I >= J 所以會break,這時 J 停留在21 [41],24,36,11,19,21(J),64,69,45,76 基準點與 J 交換 21,24,36,11,19,[41],64,69,45,76 最後再以基準點左右兩邊做相同遞迴

Java

Continue Reading

[Java]BigInteger

在寫程式時,最怕碰到數字超過現有型態的大小,且又要做運算….

Java提供了一個BigInteger物件解除大數的煩腦

Continue Reading

[Java]陣列複製 System.arraycopy

在Java中,如果陣列單純使用a = b的方式,這樣會變成參照到同一個陣列物件

如果要複製陣列內容到另一個陣列物件,可以使用System.arraycopy

System.arraycopy(來源, 起始索引, 目的, 起始索引, 複製長度)

Continue Reading

[Java]JDBC access MySQL

第一步必須先至MySQL網站下載 Connect/J的mysql-connector-java-*-bin.jar

接著加入java的classpath

root# export CLASSPATH=$CLASSPATH:完整路徑/mysql-connector-java-*-bin.jar

(*號請自行替代版本號,另外加入CLASSPATH時記得前面要補上$CLASSPATH,不然整個CLASSPATH會被mysql-connector-java-*-bin.jar蓋掉,導致java程式無法執行)

Continue Reading