Swift 排序

插入排序

func InsertSort (_ arr: inout [Int]) -> Void {
        for (i,_) in arr.enumerated() {
            if i == 0 { continue }
            let key = arr[i]
            var j = i - 1
            while j >= 0 && arr[j] > key {
                arr[j+1] = arr[j]
                j = j - 1
            }
            arr[j+1] = key
        }
    }

归并排序

func MergeSort (_ arr: inout [Int],_ left:Int,_ right :Int) -> Void {
        if left < right {
            let middle = (right-left)/2+left
            MergeSort(&arr, left, middle)
            MergeSort(&arr, middle+1, right)
            Merge(arr: &arr, left: left, middle: middle, right: right)
        }
    }
    
    func Merge(arr: inout [Int],left: Int, middle: Int,right:Int){
        let arrL = Array(arr[left...middle])
        let arrR = Array(arr[middle+1...right])
        var  l = 0
        var  r = 0
        var index = left
        
        while l < arrL.count && r < arrR.count {
            if arrL[l] < arrR[r] {
                arr[index] = arrL[l]
                l += 1
                index += 1
            } else if arrL[l] > arrR[r] {
                arr[index] = arrR[r]
                r += 1
                index += 1
            } else {
                arr[index] = arrR[r]
                r += 1
                index += 1
                arr[index] = arrL[l]
                l += 1
                index += 1
            }
        }
        
        while l < arrL.count {
            arr[index] = arrL[l]
            l += 1
            index += 1
        }
        
        while r < arrR.count {
            arr[index] = arrR[r]
            r += 1
            index += 1
        }
    }

堆排序

func heapSort(arr: inout [Int]) -> Void {
        buildMaxHeap(arr: &arr)
        var endIndex = arr.count - 1
        while endIndex > 0 {
            let temp = arr[0]
            arr[0] = arr[endIndex];
            arr[endIndex] = temp
            endIndex -= 1
            max_heapify(&arr, 0,endIndex)
        }
    }
    
    
    func parent(_ i : Int) -> Int {
        return i/2
    }
    
    func left(_ i : Int) -> Int {
        return 2*i
    }
    
    func right(_ i : Int) -> Int {
        return 2*i+1
    }
    
    func max_heapify(_ arr : inout [Int] , _ i : Int, _ size : Int) -> Void {
        
        let l = left(i)
        let r = right(i)
        var largest:Int = 0
        if l < size && arr[l] > arr[i] {
            largest = l
        }
        else {
            largest = i
        }
        if r <= size && arr[r] > arr[largest] {
            largest = r
        }
        
        if largest != i {
            arr.swapAt(largest, i)
            max_heapify(&arr, largest,size)
        }
    }
    
    func buildMaxHeap(arr: inout [Int]) -> Void {
        var i = arr.count/2
        while i >= 0 {
            max_heapify(&arr, i,arr.count-1)
            i -= 1
        }
    }

快速排序

func quickSort(arr: inout [Int],l:Int,r:Int) -> Void {
        if l < r {
            let q = partition(arr: &arr, l: l, r: r)
            quickSort(arr: &arr, l: l, r: q-1)
            quickSort(arr: &arr, l: q+1, r: r)
        }
    }
    
    func partition(arr: inout [Int],l:Int,r:Int) -> Int {
        let x = arr[r]
        var i = l
        for index in l...r {
            if arr[index] < x {
                arr.swapAt(i, index)
                i += 1
            }
        }
        arr.swapAt(i, r)
        return i
    }

计数排序

func countingSort(arr: inout [Int] , maxValueOfArr: Int) -> Void {
        var sortArr = [Int](repeating: 0, count: arr.count)
        var temp = [Int](repeating: 0, count: maxValueOfArr)
        for item in arr {
            temp[item] = temp[item]+1
        }
        
        for index in 1..<temp.count {
            temp[index] = temp[index]+temp[index-1]
        }
        
        for index in 0..<arr.count {
            sortArr[temp[arr[index]] - 1] = arr[index]
            temp[arr[index]] = temp[arr[index]] - 1
        }
        arr = sortArr
    }