棧
隊(duì)列
二分查找
插入排序
歸并排序
快速排序
棧
public struct Stack<T> {
fileprivate var array: [T] = [T]()
public var isEmpty: Bool {
return array.isEmpty
}
public var count: Int {
return array.count
}
public mutating func push(_ element: T) {
array.append(element)
}
public mutating func pop() -> T? {
return array.popLast()
}
public var top: T? {
return array.last
}
}
extension Stack: Sequence { //遍歷迭代器
public func makeIterator() -> AnyIterator<T> {
var curr = self
return AnyIterator {
return curr.pop()
}
}
}
隊(duì)列
struct Queue<T> {
fileprivate var array = [T]()
public var count: Int {
return array.count
}
public var isEmpty: Bool {
return array.isEmpty
}
public mutating func enqueue(_ element: T) { // 放入隊(duì)列
array.append(element)
}
public mutating func dequeue() -> T? { // 出隊(duì)列
if isEmpty {
return nil
}else {
return array.removeFirst()
}
}
public var front: T? {
return array.first
}
}
二分查找
二分查找是用于快速查找到目標(biāo)數(shù)據(jù)(已排序)的一種查找方式
通過(guò)取一個(gè)中間值,判斷大小, 然后將最大或最小范圍縮小至當(dāng)前位置, 再次取中間值判斷, 直到取到數(shù)據(jù)
public func binarySearch<T: Comparable>(_ a: [T], key: T) -> Int? {
var lowerBound = 0
var upperBound = a.count
while lowerBound < upperBound {
let midIndex = lowerBound + (upperBound - lowerBound) / 2 //中間值
if a[midIndex] == key {
return midIndex
} else if a[midIndex] < key {
lowerBound = midIndex + 1 // 最小值右移
} else {
upperBound = midIndex //最大值左移
}
}
return nil
}
插入排序
插入排序是遍歷第二位開(kāi)始的每一個(gè)位置上的數(shù)與 之前的數(shù)據(jù)作對(duì)比,符合條件(大于或小于)則與之交換位置, 結(jié)束滿足(位置大于0 && 當(dāng)前數(shù)比之前大或者小)
public func insectionSort<T: Comparable>(_ array: [T], sortdir: (T, T) -> Bool) -> [T] { // sortdir 返回參數(shù)比較 實(shí)現(xiàn)正序倒序 排序
var a = array
for x in 1..<array.count {
var y = x // y為當(dāng)前位置, 會(huì)依次往前遍歷
let temp = a[y]
while y > 0 && sortdir(temp, a[y - 1]) {
a[y] = a[y - 1] // 自己等于前面一個(gè)數(shù)
y -= 1 // 從自己的位置往前遍歷
}
a[y] = temp //前面沒(méi)有數(shù)再比自己小了 就放在最前面
}
return a
}
歸并排序
歸并排序, 將數(shù)組分割成一個(gè)小數(shù)組元素排序后, 再向上,將已經(jīng)擁有排序的2個(gè)數(shù)組添加到一個(gè)數(shù)組中
func mergeSort(_ arr: [Int]) -> [Int] {
guard arr.count > 1 else { return arr }
let middlle = arr.count / 2
let left = mergeSort(Array(arr[0 ..< middlle]))
let right = mergeSort(Array(arr[middlle ..< arr.count]))
return merge(left: left, right: right)
}
func merge(left: [Int], right: [Int]) -> [Int] {
var leftIndex = 0
var rightIndex = 0
var oright = [Int]() // [1, 2], [3, 4], 遍歷兩個(gè)數(shù)組按照大小組成一個(gè)
while leftIndex < left.count && rightIndex < right.count {
if left[leftIndex] < right[rightIndex] {
oright.append(left[leftIndex])
leftIndex += 1
}else if left[leftIndex] > right[rightIndex] {
oright.append(right[rightIndex])
rightIndex += 1
}else {
oright.append(left[leftIndex])
leftIndex += 1
oright.append(right[rightIndex])
rightIndex += 1
}
}
while leftIndex < left.count { //遍歷 上邊沒(méi)有遍歷完全的 全部加入數(shù)組中
oright.append(left[leftIndex])
leftIndex += 1
}
while rightIndex < right.count {
oright.append(right[rightIndex])
rightIndex += 1
}
return oright
}
快速排序
通過(guò)將數(shù)組分成三部分: 小于中間值, 等于中間值, 大于中間值, 再將左右兩部分再次分成三段, 返回為: [小于] + [等于] + [大于] 來(lái)完成排序
1.利用swift過(guò)濾函數(shù)實(shí)現(xiàn)的快速排序
func quicksort<T: Comparable>(_ a: [T]) -> [T] {
guard a.count > 1 else { return a }
let piv = a[a.count/2]
let les = a.filter{ $0 < piv }
let gras = a.filter{ $0 > piv}
let eqs = a.filter{ $0 == piv }
return quicksort(les) + eqs + gras
}
2.快速排序思想 將目標(biāo)數(shù)組用一個(gè)值將小于這個(gè)值的放在數(shù)組左邊, 大于則放在中間
func quickSockt2<T: Comparable>(_ a: inout [T], low: Int, hgt: Int) -> Int {
let pov = a[hgt] //每次都是拿去最后一個(gè)值作為參考值
var i = low // 記錄比參考值小的數(shù)據(jù)最后被換到了哪個(gè)位置
for j in i...hgt { // 遍歷從低到高的數(shù)組(一個(gè)循環(huán)完成, 數(shù)組的左邊都是比參考值小)
if a[j] < pov { //如果遍歷值 小于參考值
(a[i], a[j]) = (a[j], a[i]) // 則將小于參考值的 遍歷值放在i位置,
i += 1 //x 位置一次相加 //可以標(biāo)記最后一次交換的位置
}
}
(a[i], a[hgt]) = (a[hgt], a[i]) // 將中間值替換為參考值, 參考值最后位置替換成大于她的那個(gè)i值
return i // 標(biāo)記了中間值在什么地方
}
// 遞歸調(diào)用 通過(guò)將數(shù)組傳下去 分別在對(duì)各自已經(jīng)排序內(nèi)容排序
func quicksortLomuto<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
if low < high {
let p = quickSockt2(&a, low: low, hgt: high) // 將數(shù)組遍歷了一遍 把數(shù)組小于指定參考值值的都放在了左邊, 大于等于的則在數(shù)組的右邊, 并返回了參考值中間位置
quicksortLomuto(&a, low: low, high: p - 1) // 小于第一次指定參考值的被放在左邊, 這里再重新列為一個(gè)數(shù)組 再次找出指定值, 再實(shí)現(xiàn)分組
quicksortLomuto(&a, low: p + 1, high: high) // 遞歸調(diào)用到低位置不小與高位置為止
}
}
