归并排序&快速排序

class 归并排序{
    
    func sort(arr:[Int]) ->[Int]{
        guard arr.count > 1 else { return arr }
        //1 分解,采用左开右必原则
        let mid = (arr.count) / 2
        let leftArr = sort(arr: Array.init(arr[0 ..< mid])) //
        let rightArr = sort(arr: Array.init(arr[mid ..< arr.count ]))
        //合并
        return merge(leftArr: leftArr, rightArr: rightArr)
    }
    func merge(leftArr:[Int],rightArr:[Int]) ->[Int]{
        var finalArr = [Int]()
        var leftIndex = 0
        var rightIndex = 0
        while leftIndex < leftArr.count && rightIndex < rightArr.count { //终止条件 这里要并且(出现过错误,检查好久)
            if leftArr[leftIndex] < rightArr[rightIndex]{
                finalArr.append(leftArr[leftIndex])
                leftIndex += 1
            }else{
                finalArr.append(rightArr[rightIndex])
                rightIndex += 1
            }
        }
        //如果左边指针,或者右边指针指向数组末尾,则排序完毕,添加另外一个没有访问完毕的数组,并加入到final里面,最开始忘记加,半夜脑子不好使(错误二)
        if leftIndex == leftArr.count{
            finalArr += rightArr[rightIndex...]
        }else{
            finalArr += leftArr[leftIndex...]
        }
        return finalArr
    }
    
}


        let sort = 归并排序()
        let final = sort.sort(arr: [9,1,2,31,32,23,44,12,321,45])
        print(final)
//[1, 2, 9, 12, 23, 31, 32, 44, 45, 321]


class 快速排序 {
    func quickSort( array:inout Array<Int>, begin:Int,end:Int){
        guard begin < end else {return}
        var b = begin
        var e = end
        let povit = array[begin]
        while b < e {
            while  b < e { //这里面要写b<e,查找了好半天
                if array[e] > povit{//右边比轴点元素大,不动,end-1
                    e -= 1
                }else{//右边比point小,将end放到begin位置
                    array[b] = array[e]
                    b += 1
                    break
                }
            }
            while  b < e {
                if array[b] < povit { //左边比轴点小,不用动 begin+1
                    b += 1
                }else{
                    array[e] = array[b]
                    e -= 1
                    break
                }
            }
            
        }
        array[b] = povit
        quickSort(array: &array, begin: begin, end: b - 1)
        quickSort(array: &array, begin: b + 1, end: end )
    }

}