排序问题

/// 冒泡排序
func bubbleSort<T>(_ array: [T]) -> [T] where T: Comparable{
    var array = array
    guard array.count > 1 else {
        return array
    }
    for i in 0..<array.count {
        //提前退出标志
        var flag: Bool = false
        for j in 0..<array.count - i - 1 {
            if array[j] > array[j + 1] {
                array.swapAt(j + 1, j)
                //有数据交换
                flag = true
            }
        }
        //没有数据交换-提前退出
        if flag == false {
            break
        }
    }
    return array
}

///插入排序
func insertSort<T>(_ elements: [T]) -> [T] where T: Comparable {
    var array = elements
    guard array.count > 1 else {
        return array
    }
    for i in 1..<array.count {
        let value = array[i]
        var j = i - 1
        //查找要插入的位置
        for p in (0...j).reversed() {
            if array[p] > value {
                array[p+1] = array[p]//移动数据
            } else {
                break
            }
        }
        array[j+1] = value// 插入数据
    }
    return array
}

func merge(_ leftArray: [Int], _ rightArray: [Int]) -> [Int] {
    //1
    var l = 0, r = 0
    //2
    var mergeArr: [Int] = []
    //3
    while l < leftArray.count && r < rightArray.count {
        if leftArray[l] > rightArray[r] {
            mergeArr.append(rightArray[r])
            r += 1
        } else if leftArray[l] < rightArray[r] {
            mergeArr.append(leftArray[l])
            l += 1
        } else {
            mergeArr.append(leftArray[l])
            l += 1
            mergeArr.append(rightArray[r])
            r += 1
        }
    }
    //4
    while l < leftArray.count {
        mergeArr.append(leftArray[l])
        l += 1
    }
    while r < rightArray.count {
        mergeArr.append(rightArray[r])
        r += 1
    }
    return mergeArr
}
/*
 1、如果数组为空或包含单个元素，则无法将其拆分为更小的部分，返回数组就行。

 2、找到中间索引。

 3、使用上一步中的中间索引，递归地分割数组的左侧。

 4、递归地分割数组的右侧。

 5、最后，将所有值合并在一起，确保它始终排序。
 */
func mergeSort(_ array: Array<Int>) -> Array<Int> {
    //1
    guard array.count > 1 else {
        return array
    }
    //2
    let middle = array.count / 2
    //3
    let leftPart = mergeSort(Array(array[0..<middle]))
    //4
    let rightPart = mergeSort(Array(array[middle..<array.count]))
    //5
    return merge(leftPart, rightPart)
}

func quickSort<T: Comparable>(_ array: [T]) -> [T]{

    let pivot = array[array.count / 2]

    let less = array.filter { $0 < pivot }
    let equal = array.filter { $0 == pivot }
    let more = array.filter { $0 > pivot }

    return quickSort(less) + equal + quickSort(more)
}

/*
 1、从序列中选择中轴点pivot（假设选择位置为0的元素）
 2、利用pivot中轴点把序列分成两个子序列
 3、分别对左右子序列递归进行快速排序，直到元素不能分割位置
   快速排序的本质是把每一个元素都转换成中轴点。
 */
public func quickSortDutch<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
    if low < high {
        let pivot = Int.random(in: low...high)
        let (p, q) = partationDutch(&a, low: low, high: high, pivotIndex: pivot)
        quickSortDutch(&a, low: low, high: p - 1)
        quickSortDutch(&a, low: q + 1, high: high)
    }
}

/*

 3 荷兰国旗分区：将前部和后部各排在数组的前边和后边，中部自然就排好了,分区函数返回(p, q)

 设置两个标志位begin和end分别指向这个数组的开始和末尾，然后用一个标志位current从头开始进行遍历：

 1）若遍历到的current < pivot，于是就和begin位置进行交换，然后current向前进，begin也向前进（表示前边的已经都排好了）。

 2）若遍历到current == pivot，则说明它一定属于中部，根据总思路，中部的我们都不动，然后current向前进。

 3）若遍历到current > pivot，则说明它一定属于后部，于是就和end位置进行交换，
    由于交换完毕后current指向的可能是属于前部的，若此时current前进则会导致该位置不能被交换到前部，所以此时current不前进。
    end向后退1。

 4) 返回分区（begin, end）
 */
func partationDutch<T: Comparable>(_ a: inout [T], low: Int, high: Int, pivotIndex: Int) -> (Int, Int) {
    var begin = low, end = high
    var current = low, pivot = a[pivotIndex]
    while current <= end {
        if a[current] < pivot {
            a.swapAt(begin, current)
            begin += 1
            current += 1
        } else if a[current] == pivot {
            current += 1
        } else {
            a.swapAt(current, end)
            end -= 1
        }
    }
    return (begin, end)
}