栈
队列
二分查找
插入排序
归并排序
快速排序
栈
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()
}
}
}
队列
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) { // 放入队列
array.append(element)
}
public mutating func dequeue() -> T? { // 出队列
if isEmpty {
return nil
}else {
return array.removeFirst()
}
}
public var front: T? {
return array.first
}
}
二分查找
二分查找是用于快速查找到目标数据(已排序)的一种查找方式
通过取一个中间值,判断大小, 然后将最大或最小范围缩小至当前位置, 再次取中间值判断, 直到取到数据
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
}
插入排序
插入排序是遍历第二位开始的每一个位置上的数与 之前的数据作对比,符合条件(大于或小于)则与之交换位置, 结束满足(位置大于0 && 当前数比之前大或者小)
public func insectionSort<T: Comparable>(_ array: [T], sortdir: (T, T) -> Bool) -> [T] { // sortdir 返回参数比较 实现正序倒序 排序
var a = array
for x in 1..<array.count {
var y = x // y为当前位置, 会依次往前遍历
let temp = a[y]
while y > 0 && sortdir(temp, a[y - 1]) {
a[y] = a[y - 1] // 自己等于前面一个数
y -= 1 // 从自己的位置往前遍历
}
a[y] = temp //前面没有数再比自己小了 就放在最前面
}
return a
}
归并排序
归并排序, 将数组分割成一个小数组元素排序后, 再向上,将已经拥有排序的2个数组添加到一个数组中
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], 遍历两个数组按照大小组成一个
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 { //遍历 上边没有遍历完全的 全部加入数组中
oright.append(left[leftIndex])
leftIndex += 1
}
while rightIndex < right.count {
oright.append(right[rightIndex])
rightIndex += 1
}
return oright
}
快速排序
通过将数组分成三部分: 小于中间值, 等于中间值, 大于中间值, 再将左右两部分再次分成三段, 返回为: [小于] + [等于] + [大于] 来完成排序
1.利用swift过滤函数实现的快速排序
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.快速排序思想 将目标数组用一个值将小于这个值的放在数组左边, 大于则放在中间
func quickSockt2<T: Comparable>(_ a: inout [T], low: Int, hgt: Int) -> Int {
let pov = a[hgt] //每次都是拿去最后一个值作为参考值
var i = low // 记录比参考值小的数据最后被换到了哪个位置
for j in i...hgt { // 遍历从低到高的数组(一个循环完成, 数组的左边都是比参考值小)
if a[j] < pov { //如果遍历值 小于参考值
(a[i], a[j]) = (a[j], a[i]) // 则将小于参考值的 遍历值放在i位置,
i += 1 //x 位置一次相加 //可以标记最后一次交换的位置
}
}
(a[i], a[hgt]) = (a[hgt], a[i]) // 将中间值替换为参考值, 参考值最后位置替换成大于她的那个i值
return i // 标记了中间值在什么地方
}
// 递归调用 通过将数组传下去 分别在对各自已经排序内容排序
func quicksortLomuto<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
if low < high {
let p = quickSockt2(&a, low: low, hgt: high) // 将数组遍历了一遍 把数组小于指定参考值值的都放在了左边, 大于等于的则在数组的右边, 并返回了参考值中间位置
quicksortLomuto(&a, low: low, high: p - 1) // 小于第一次指定参考值的被放在左边, 这里再重新列为一个数组 再次找出指定值, 再实现分组
quicksortLomuto(&a, low: p + 1, high: high) // 递归调用到低位置不小与高位置为止
}
}
