排序算法

冒泡排序

func bubbleSort<T: Comparable>(arr: [T]) -> [T] {
    guard arr.count > 1 else {return arr}
    var newArr = arr
    for i in 0..<newArr.count {
        for j in (i+1)..<arr.count {
            if newArr[i] > newArr[j] {
                let temp = newArr[i]
                newArr[i] = newArr[j]
                newArr[j] = temp
            }
        }
    }
    return newArr
}

插入排序

func insertSort<T: Comparable>(arr:[T]) -> [T] {
    guard arr.count > 1 else {return arr}
    var array = arr // make it mutable
    for i in 1..<array.count {
        for j in stride(from: i, to: 0, by: -1) {
            if array[j] < array[j - 1] {
                let temp = array[j]
                array[j] = array[j - 1]
                array[j - 1] = temp
            }
        }
    }
    return array
}

选择排序

func selectSort<T: Comparable>(arr:[T]) -> [T] {
    guard arr.count > 1 else {return arr}
    var array = arr
    
    for i in 0..<array.count {
        for j in i..<array.count {
            if array[j] < array[i] {
                let temp = array[j]
                array[j] = array[i]
                array[i] = temp
            }
        }
    }
    return array
}

归并排序

func merge<T: Comparable>(left: [T], right: [T]) -> [T] {
    var arr = [T]()
    
    var i = 0
    var j = 0
    while i < left.count && j < right.count {
        if left[i] < right[j] {
            arr.append(left[i])
            i += 1
        } else {
            arr.append(right[j])
            j += 1
        }
    }
    
    if i < left.count {
        for index in i..<left.count {
            arr.append(left[index])
        }
    } else {
        for index in j..<right.count {
            arr.append(right[index])
        }
    }
    
    return arr
}
func mergeSort<T: Comparable>(a:[T]) -> [T] {
    if a.count  < 2 {
        return a
    }
    let mid = a.count / 2
    let left = Array(a[0..<mid])
    let right = Array(a[mid..<a.count])
    return merge(left: mergeSort(a: left), right: mergeSort(a: right))
}

堆排序

class Heap<T: Comparable> {
    var nodes: [T]
    var sortCriteria: ((T,T) -> Bool)
    func shiftDown(index: Int, endIndex: Int) {
        let left = leftchildIndex(index: index)
        let right = rightchildIndex(index: index)
        if left <= endIndex && sortCriteria(nodes[left], nodes[index]) {
            self.nodes.swapAt(index, left)
            shiftDown(index: left, endIndex: endIndex)
        }
        if right <= endIndex && sortCriteria(nodes[right], nodes[index]) {
            self.nodes.swapAt(index, right)
            shiftDown(index: right, endIndex: endIndex)
        }
    }
    
    func leftchildIndex(index: Int) -> Int {
        return index * 2 + 1
    }
    
    func rightchildIndex(index: Int) -> Int {
        return index * 2 + 2
    }
    
    func sort() -> [T] {
        guard self.nodes.count > 1 else { return self.nodes }
        
        for i in stride(from: self.nodes.count - 1, through: 1, by: -1 ) {
            shiftDown(index: 0, endIndex: i)
            nodes.swapAt(0, i)
        }
        return self.nodes
    }
    

    init(arr:[T], sort: @escaping (T,T) -> Bool) {
        self.nodes = arr
        self.sortCriteria = sort

        for i in stride(from: arr.count / 2 - 1, through: 0, by: -1) {
            shiftDown(index: i, endIndex: self.nodes.count - 1)
        }
    }
}


func heapSort<T: Comparable>(a: [T]) -> [T] {
    
    return  Heap.init(arr: a, sort: >).sort()
}