交换排序

让每个值都和它后面的值比较，如果打则交换，这样第一位置的值在一次循环后就是最小值，然后第二次循环找出第二小的值，以此类推。

交换排序

func switchSort(_ array: inout [Int]) -> [Int] {
    
    guard array.count > 1 else { return array }
    
    for i in 0 ..< array.count {
        
        for j in i + 1 ..< array.count {
          
            if array[i] > array[j] {
                array.swapAt(i, j) 
                print("\(array)")
            }
        }
    }
    
    return array 
}

冒泡排序

两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
O(n2)

冒泡排序

func bubbleSort(_ array: inout [Int]) -> [Int] {
    
    guard array.count > 1 else { return array }    
    
    for i in 0 ..< array.count - 1 {

        for j in 0 ..< array.count - 1 - i {
            
            if array[j] > array[j+1] {
                array.swapAt(j, j+1) //keeping index of j is the smaller one
                print("after swap: \(array)")
                
            }
        }
    }
    return array
}

// 优化冒泡
func bubbleSortAdvanced(_ array: inout [Int]) -> [Int] {
    
    guard array.count > 1 else { return array }
    
    for i in 0 ..< array.count - 1 {
        
        //bool switch
        var swapped = false
      
        for j in 0 ..< array.count - i - 1 {
            
            if array[j] > array [j+1] {
                array.swapAt(j, j+1) 
                swapped = true;
            }
        }
        
        //if there is no swapping in inner loop, it means the the part looped is already sorted,
        //so it's time to break
        if (swapped == false){ break }
    }
    
    return array
    
}

选择排序

O(n2)
两层循环，外面循环开始时用变量min记录最小值对应的下标，初始化为i，然后每次内层循环来得到最小值对应下标。如果最小值下标变化了说明找到了比i对应的值更小的值，这时候替换i与min对应的值。否则说明i对应的就是这次外层循环对应的最小值，不用替换。

func selectionSort(_ array: inout [Int]) -> [Int] {
    
    guard array.count > 1 else { return array }

    for i in 0 ..< array.count - 1{
        
        var min = i
        
        for j in i + 1 ..< array.count {
            
            if array[j] < array[min] {
                min = j 
            }
        }
        
        //if min has changed, it means there is value smaller than array[min]
        //if min has not changed, it means there is no value smallter than array[min]
        if i != min {
            array.swapAt(i, min) 
        }
    }
    return array
}

插入排序

从数组中拿出一个元素（通常就是第一个元素）以后，再从数组中按顺序拿出其他元素。如果拿出来的这个元素比这个元素小，就放在这个元素左侧；反之，则放在右侧。

func insertionSort(_ array: inout [Int]) -> [Int] {
    
    guard array.count > 1 else { return array }
    
    for i in 1..<array.count {
        
        var j = i
        while j > 0 && array[j] < array[j - 1] {
             array.swapAt(j - 1, j)
            j -= 1
        }
    }
    return array
}

归并排序

归并排序示意图

递归实现

func mergeSort(array: [Int]) -> [Int] {
    var helper = Array(repeating: 0, count: array.count)
    var array = array
    mergeSort(array: &array, helper: &helper, start: 0, end: array.count - 1)
    return array
}

func mergeSort(array: inout [Int], helper: inout [Int], start: Int, end: Int) {
    // 递归基础，当start大于等于end的时候说明已经分为最小单位
    if start >= end {
        return
    }
    let m = (start + end) / 2
    // 排序start到m
    mergeSort(array: &array, helper: &helper, start: start, end: m)
    // 排序m+1到end
    mergeSort(array: &array, helper: &helper, start: m + 1, end: end)
    // 归并start到m的数组与m+1到end的数组
    merge(array: &array, helper: &helper, start: start, middle: m, end: end)
}

func merge(array: inout [Int], helper: inout [Int], start: Int, middle: Int, end: Int) {
    // copy both halves into a helper array
    for i in start ... end {
        helper[i] = array[i]
    }

    // 标记左侧start~middle中要取出元素的位置
    var helperLeft = start
    // 标记右侧middle+1~end中要取出元素的位置
    var helperRight = middle + 1
    // 标记当前排序的位置
    var current = start
    
    // 取出左右两侧中较小的元素放到当前排序的位置，排好以后排下一个位置
    while helperLeft <= middle && helperRight <= end {
        if helper[helperLeft] <= helper[helperRight] {
            array[current] = helper[helperLeft]
            helperLeft += 1
        } else {
            array[current] = helper[helperRight]
            helperRight += 1
        }
        current += 1
    }
    
    // 归并剩下的元素放到排好序的元素后面
    if helperLeft <= middle {
        for i in 0...(middle - helperLeft) {
            array[current + i] = helper[helperLeft + i]
        }
    }
    if helperRight <= end {
        for i in 0...(end - helperRight) {
            array[current + i] = helper[helperRight + i]
        }
    }
}

merge函数示意图
其中 k = current, i = helperLeft, j = helperRight, m = niddle, n = end

非递归实现
//todo

快速排序

func _QSort(array: inout [Int]) {
    qSort(array: &array, low: 0, high: array.count - 1)
}

func qSort(array: inout [Int], low: Int, high: Int) {
    if low >= high {
        return
    }
    
    // 查找枢轴点，并把数组以其分为两部分，左侧全部小于枢轴，右侧全部大于枢轴
    let pivot = partition(array: &array, low: low, high: high)
    
    // 对枢轴左侧进行排序
    qSort(array: &array, low: low, high: pivot - 1)
    // 对枢轴右侧进行排序
    qSort(array: &array, low: pivot + 1, high: high)
}

// 查找枢轴记录
func partition(array: inout [Int], low: Int, high: Int) -> Int {
    var low = low
    var high = high
    
    // 使用第一个元素作为枢轴记录
    let pivotValue = array[low]
    // 从低到高遍历
    while low < high {
        // 从高开始查找，找到第一个比枢轴小的点跳出循环
        while low < high && array[high] >= pivotValue {
            high -= 1
        }
        // low现在代表的是枢轴所在的位置，这时高点指向的值比枢轴小，
        // 因此交换枢与高点的位置，交换之后高点high表示枢轴的位置
        array.swapAt(low, high)
        // 从低点开始查找，找到第一个比枢轴大的点后跳出循环
        while low < high && array[low] <= pivotValue {
            low += 1
        }
        // 交换低点与枢轴的位置，交换以后低点low表示枢轴的位置
        array.swapAt(high, low)
    }
    // 跳出上面的循环说明高点低点重合了，这时就表明比枢轴小的都处于左侧，比其大的都处于右侧
    return low
}

partition 函数示意