栈
队列
二分查找
插入排序
归并排序
快速排序

栈

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) // 递归调用到低位置不小与高位置为止
  }
}