歡迎來到 Swift 演算法社團

在這裡你將找到一些普及的演算法和資料結構在 Swift 上的實作，附帶詳細的解釋.

如果你是需要這些知識來準備考試的學生 -- 或者你是個想要自我學習的程式設計人員 -- 那你來對地方了!

這個專案的目的是 解釋演算法是如何運作.重點放在程式碼的清晰和可讀性，並非製作可重複使用的函式庫能讓你直接放到你的專案中.就算這樣說，大部分的程式碼應該都可以正式使用，但是你可能要調整一下.

所有的程式碼皆可以在 Xcode 7.3 和 Swift 2.2 上執行.我們將依據最新的 Swift 版本做更新.

這是個正在進行的專案，近期將會新增更多演算法. :-)

😍 歡迎任何建議和貢獻 😍

重要連結

[什麼是演算法和資料結構?](What are Algorithms.markdown) 蛋糕!

[為什麼要學演算法?](Why Algorithms.markdown) 煩惱吸收不良? 看看這個.

[Big-O 表示法](Big-O Notation.markdown). 我們常說 "這個演算法複雜度是 O(n)." 如果你不知道是什麼意思, 先看看個.

[演算法設計技巧](Algorithm Design.markdown). 如何創造自己的演算法?

[如何貢獻](How to Contribute.markdown). 給我們反饋, 或來一個PR.

[施工中](Under Construction.markdown). 還在建構中的演算法.

從何下手?

如果你對演算法和資料結構非常陌生，這有幾個不錯的起點:

堆疊
佇列
[插入排序](Insertion Sort/)
[二元搜尋](Binary Search/) 和 [二元搜尋樹](Binary Search Tree/)
[合併排序](Merge Sort/)
Boyer-Moore 字串搜尋

演算法

搜尋

[線性搜尋](Linear Search/). 在陣列中找到元素.
[二元搜尋](Binary Search/). 在排序過的陣列中快速找到元素.
[發生次數](Count Occurrences/). 計算某個值在陣列中出現幾次.
[選取最小值 / 最大值](Select Minimum Maximum). 找到陣列中的最小值/最大值.
[第K大的值](Kth Largest Element/). 在陣列中，找到第 k 大的元素，例如中位數.
[選擇採樣](Selection Sampling/). 隨機在集合中選取一堆元素.
聯集查找. 追蹤沒交集的集合，並快速合併它們.
Z-Algorithm. 在給定字串中找到符合搜尋字串, 並回傳所有符合字串的起始索引.

字串搜尋

[Brute-Force 字串搜尋](Brute-Force String Search/). 一個簡單暴力的方法.
Boyer-Moore. 一個快速搜尋子字串的方法. 為了避免走訪每個字元，根據查表來跳過某些的部分.
Knuth-Morris-Pratt
Rabin-Karp
[最長共同子字串](Longest Common Subsequence/). 找到兩個字串中相同部分最長的子字串.

排序

研究排序演算法的原理是非常有趣的，但是在實做中，你幾乎不會需要去碰到這部分.Swift 自帶的 sort() 就已經很夠用了，但是如果你有興趣，請繼續閱讀...

基本排序演算法:

[插入排序](Insertion Sort/)
[選擇排序](Selection Sort/)
[Shell 排序](Shell Sort/)

快速排序演算法:

快速排序
[合併排序](Merge Sort/)
[堆積排序](Heap Sort/)

Special-purpose sorts:

特殊目的排序演算法:

[Counting Sort](Counting Sort/)
Radix Sort
[Topological Sort](Topological Sort/)
[計數排序](Counting Sort/)
Radix Sort
[*拓樸排序](Topological Sort/)

糟糕的排序演算法 (知道就好，不要使用!):

[氣泡排序](Bubble Sort/)
[*緩慢排序](Slow Sort/)

壓縮

[運行長度編碼 (RLE)](Run-Length Encoding/). 將重複的值儲存為一個 byte 並計數.
[Huffman 編碼](Huffman Coding/). 將常出現的值用較小的值來儲存.

雜項

*洗牌. 隨機重排陣列中的元素.
[*梳排序](Comb Sort/). 氣泡排序法進化.

*數學導向

最大公因數 (GCD). 加碼: 最小公倍數.
排列組合. 回顧學過的排列組合吧!
[*分流場](Shunting Yard/). 將中序式表示法轉換為後序式表示法.
統計
[Karatsuba 快速乘法](Karatsuba Multiplication/). 另一種基礎乘法.
Haversine 距離. 計算球體上兩點的距離.

機器學習

k-Means 叢集. 非監督式分類，將數據分成 k 群集.
k-Nearest 鄰近
[線性迴歸](Linear Regression/)
邏輯迴歸
神經網路
網頁排名

資料結構

對於資料結構和特定任務的選擇依據幾件事情.

首先，你的資料是具有某種形態，並且有一些必要的操作方法. 如果你想要依照某個 key 值去找到物件，那你需要字典類型的結構; 如果你的資料有分層特徵，你那會想要類似樹狀結構; 如果你的資料是序列，那你需要堆疊或佇列結構.

第二，你的資料需要一些特別的操作，不同的結構對於優化的操作都不盡相同.舉例來說，如果你常需要獲得集合中最重要的元素，那使用堆積或優先佇列就會比單純的陣列還要好.

大多數情況下，內建的 Array、Dictionary 和 Set 已經足夠，但有時候你會需要更特殊的結構.

陣列的變化

二維陣列. 固定大小的二維陣列，可用於棋盤遊戲中.
[位元集](Bit Set/). 含有 n 個位元的序列.
[固定長度陣列](Fixed Size Array/). 如果可以確定資料量大小，那使用傳統的固定長度陣列會具有更高的效能.
[有序陣列](Ordered Array/). 一個已經排序過的陣列.
[Rootish Array Stack](Rootish Array Stack/). 在空間和時間上優化的 Swift 陣列.

佇列

堆疊. 後進先出.
佇列. 先進先出.
雙端佇列. 可選擇在陣列的前端或尾端新增或取得元素.
[優先佇列](Priority Queue). 最重要的元素永遠在最前端.
[環狀緩衝](Ring Buffer/). 一個頭尾相接的陣列.

列表

[鏈結列表](Linked List/). 內容元素以鏈結來銜接的序列，包含單向及雙向.
跳躍列表. 這是一種機率性的資料結構, 提供對數時間複雜度, 並且擁有 AVL 或紅黑樹的效能, 還有支援聰明又有效率的搜尋及更新的操作.

樹

樹. 一般性的樹狀結構.
[二元樹](Binary Tree/). 每個節點最多只有兩個子節點的樹.
[二元搜尋樹 (BST)](Binary Search Tree/). 節點經過排序的二元樹，優化了搜尋速度.
紅黑樹
展開樹
螺旋二元樹
[分割樹](Segment Tree/). 可以快速的對陣列中的某區間進行計算.
kd 樹
堆積. 儲存在一維陣列中的二元樹，不需要指標，很適合做優先佇列.
費波那契堆積
字典樹
B 樹. 自平衡搜尋樹，每個節點可以擁有超過兩個子節點.

雜湊

[雜湊表](Hash Table/). 可以使用 key 值來儲存或取得物件，字典通常是使用雜湊表實現的.
雜湊函數

集合

[布隆過濾器](Bloom Filter/).可以用於檢索一個元素是否在一個集合中.它的優點是空間效率和查詢時間都遠遠超過一般的演算法，缺點是有一定的誤識別率和刪除困難.
[雜湊集合](Hash Set/). 使用雜湊表實做.
多重集合
[有序集合](Ordered Set/). 元素有順序的集合.

圖

圖
[廣度優先搜尋 (BFS)](Breadth-First Search/)
[深度優先搜尋 (DFS)](Depth-First Search/)
[最短路徑](Shortest Path %28Unweighted%29/) 在未加權的樹上討論
[單源最短路徑](Single-Source Shortest Paths (Weighted)/)
[最小生成樹](Minimum Spanning Tree %28Unweighted%29/) 在未加權的樹上討論
[任意兩點最短路徑](All-Pairs Shortest Paths/)

動腦時間

許多軟體開發者在面試時都會被問到一些演算法的問題，這裡只收集了一些有趣的題目，想瞭解更多這類的問題 (及答案)，請瀏覽這裡和這裡.

[雙和問題](Two-Sum Problem/)
[Fizz Buzz](Fizz Buzz/)
[蒙提霍爾問題](Monty Hall Problem/)
尋找迴文
Dining Philosophers

許可證

本專案包含原專案都是基於 MIT 協議，請隨意使用!

By posting here, or by submitting any pull request through this forum, you agree that all content you submit or create, both code and text, is subject to this license. Razeware, LLC, and others will have all the rights described in the license regarding this content. The precise terms of this license may be found here.

vulcanshen/swift-algorithm-club-zhTW