排序算法【 Swift 实现】

冒泡排序

//加flag使得完全顺序循环一次就退出
func bubbleSort(_ list: inout [Int], _ n: Int) {
    if (n <= 1) {return}
    for i in 0..<n {
        var flag = false
        for j in 0..<n-i-1 {
            if (list[j] > list[j+1]) {
                list.swapAt(j, j+1)
                flag = true
            }
        }
        if !flag {
            break
        }
    }
}

插入排序

func insertionSort(_ list: inout [Int], _ n: Int) {
    if (n <= 1) {return}
    for i in 1..<n {
        let tmp = list[i]
        var j = i - 1
        while j>=0 {
            if (tmp < list[j]) {
                list[j+1] = list[j]
            } else {
                break
            }
            j -= 1
        }
        list[j+1] = tmp
    }
}

选择排序

func chooseSort(_ list: inout [Int], _ n: Int) {
    if (n <= 1) {return}
    for i in 0..<n {
        var min = list[i]
        var index = i
        for j in i..<n {
            if(list[j] < min) {
                min = list[j]
                index = j
            }
        }
        list.swapAt(i, index)
    }
}

归并排序

func mergeSort(_ list: inout [Int], _ n: Int) {
    var helper = Array(repeating: 0, count: n)
    mergeSortC(&list, &helper, 0, n-1)
}
func mergeSortC(_ list: inout [Int], _ helper: inout [Int], _ low: Int, _ high: Int) {
    guard low < high else {
        return
    }
    let middle = (high - low) / 2 + low
    mergeSortC(&list, &helper, low, middle)
    mergeSortC(&list, &helper, middle + 1, high)
    merge(&list, &helper, low, middle, high)
}
func merge(_ list: inout [Int], _ helper: inout [Int], _ low: Int, _ middle: Int, _ high: Int) {
    for i in low ... high {
        helper[i] = list[i]
    }
    var left = low, right = middle + 1, current = low
    while left <= middle && right <= high {
        if helper[left] <= helper[right] {
            list[current] = helper[left]
            left += 1
        } else {
            list[current] = helper[right]
            right += 1
        }
        current += 1
    }

    guard middle - left >= 0 else {
        return
    }
    for i in 0...middle - left {
        list[current + i] = helper[left + i]
    }
}

快速排序

func quickSort(_ array: [Int]) -> [Int] {
    guard array.count > 1 else {
        return array
    }
    let pivot = array[array.count / 2]
    let left = array.filter { $0 < pivot }
    let middle = array.filter { $0 == pivot }
    let right = array.filter{ $0 > pivot }
    
    return quickSort(left) + middle + quickSort(right)
}

//减低空间复杂度版
func quickSort(_ array: inout [Int], _ n: Int) {
    quickSortC(&array, 0, n - 1)
}

func quickSortC(_ array: inout [Int], _ left: Int, _ right: Int) {
    if left >= right {return}
    let pivot = partition(&array, left, right)
    quickSortC(&array, left, pivot - 1)
    quickSortC(&array, pivot + 1, right)
}

func partition(_ array: inout [Int], _ left: Int, _ right: Int) -> Int {
    let pivot = array[right]
    var i = left
    for j in left ..< right {
        if (array[j] < pivot) {
            array.swapAt(j, i)
            i += 1
        }
    }
    array.swapAt(i, right)
    return i
}