Category Archives: DataStructure

[DataStructure]HeapSort(堆積排序)

HeapSort是利用堆積樹(Heap Tree)的性質來排序,堆積樹為完全二元樹(Complete Binary Tree)的一種,父節點大於兩個子節點稱為最大堆積樹,反之則稱為最小堆積樹

HeapSort原理就是將堆積樹根(最大or小值)與最後一個節點調換,將最後一個節點(原樹根)取出,並加入已排序數列,再將樹調整為堆積樹

最小堆積樹程式步驟: 1.由根或葉走訪二元樹 2.如遇子節點比父節點小時,子節點與父節點交換 3.遞迴繼續往樹根比 4.回到原本二元樹的走訪

HeapSort程式步驟: 1.將二元樹排列成堆積樹 2.根與葉交換,取出葉(原先的根) 3.重新排列堆積樹 4.重複

Continue Reading

[DataStructure]BFS(廣度優先)

BFS主要邏輯

從樹根開始當母節點 把子節點塞進queue 把一開始的母節點紀錄起來 從queue拉出子節點繼續

當然如果是做子圖的話還需要判斷該節點是否已經走訪過了

範例: Java簡易二元樹BFS走訪

Continue Reading

[DataStructure]LinkedList(鏈結串列)

LinkedList是一種常見的資料結構,它的特性是在不連續的記憶體空間中保有連續性的資料

另外LinkedList也不需要特別定義串列長度,隨時可以做新增修改刪除

Java範例 LinkedList.java

index.java

Continue Reading

[DataStructure]BinaryTree(二元樹)

二元樹可以利用連結串列或陣列來表示

鏈結串列可以直接定義parent、left、right三種變數來紀錄父節點和子節點 陣列擺放節點有一定的公式,且陣列[0]不使用

Java陣列二元樹走訪

Continue Reading

[DataStructure]Towers of Hanoi(河內塔)

河內塔是一個數學遊戲:有三個塔柱A、B、C,遊戲的目的就是將A塔柱的圓盤全數移到C塔柱

遊戲有幾個規則: 1. 一次只能搬移一個圓盤 2. 小圓盤可以移到大圓盤上面,大圓盤不可以移到小圓盤上面。

事實上,可以從河內塔移動次數中,發現這是有遞迴規則的。 以最小的圓盤 n 為例: 當圓盤總數為 1 時, n 移動了 1 次 當圓盤總數為 2 時, n 移動了 2 次 當圓盤總數為 3 時, n 移動了 4 次 當圓盤總數為 4 時, n 移動了 8 次

為了要讓大盤可以移出來到目的柱,當盤數越多,其他較小圓盤就必須先移到暫存柱(三柱其中一柱) 若有n個盤子,則移動完畢所需的次數為2^n – 1

Java

Continue Reading

[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

[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