Swift-冒泡排序、快速排序、归并排序、二分查找

冒泡排序

冒泡排序

var sortArr: [Int] = [23,523,11,98,1,54,83,22]
func bubbleSort(_ array:[Int]) -> [Int]{
    var sortArr:[Int] = array
    for i in 0..<sortArr.count {
        if i+1 > sortArr.count {return sortArr}
        for j in i+1..<sortArr.count {
            if sortArr[i]>sortArr[j] {
                sortArr.swapAt(i, j)
            }
        }
    }
    return sortArr
}
bubbleSort(sortArr)

快速排序

快速排序

func quickSort(_ array:inout [Int], left:Int, right:Int) {
    guard left < right else {
        return
    }
    var i = left
    var j = right
    let tmpVal = array[left]
    
    while i < j {
        while i < j && array[j] >= tmpVal {
            j -= 1
        }
        while i < j && array[i] <= tmpVal {
            i += 1
        }
        if i < j  {
            array.swapAt(i, j)
        }
    }
    array[left] = array[i]
    array[i] = tmpVal
    
    quickSort(&array, left: left, right: i)
    quickSort(&array, left: i+1, right: right)
}
quickSort(&sortArr, left: 0, right: sortArr.count-1)

归并排序

归并排序

func mergeSort(_ array:[Int]) -> [Int] {
    if array.count <= 1 {
        return array
    }
    let length = array.count
    let mid = (length-1)/2
    let leftArr = mergeSort(Array(array[0...mid]))
    let rightArr = mergeSort(Array(array[mid+1...length-1]))
    let outArr = merge(leftArr, rightArr)
    print("leftArr-------\(leftArr),rightArr--------\(rightArr),outArr------\(outArr)")
    return outArr
}

func merge(_ array1: [Int], _ array2: [Int]) -> [Int]{
    var tmpArr = Array<Int>()
    var i = 0
    var j = 0
    
    while i<array1.count && j<array2.count {
        if array1[i]<array2[j] {
            tmpArr.append(array1[i])
            i += 1
        }else{
            tmpArr.append(array2[j])
            j += 1
        }
    }
    
    if i == array1.count {
        tmpArr += array2[j...array2.count-1]
    }else{
        tmpArr += array1[i...array1.count-1]
    }
    print("tmpArr-------\(tmpArr),array1------\(array1),array2------\(array2)")
    return tmpArr
}
mergeSort(sortArr)

二分查找

func halfSearch(_ array:[Int], keyVal:Int) -> Int {
    
    if array.count <= 1 {
        return 0
    }
    
    var mid = (array.count-1)/2
    var left = 0
    var right = array.count-1
    
    while left < right {
        if array[left] == keyVal {
            return left
        }
        if array[right] == keyVal {
            return right
        }
        if array[mid] == keyVal {
            return mid
        }else if keyVal < array[mid] {
            right = mid
        }else{
            left = mid
        }
        mid = (right+left)/2
        print("left-------\(left),mid----------\(mid),right-----------\(right)")
    }
    return -1
}
halfSearch(mergeSort(sortArr), keyVal: 11)