/*
 冒泡排序：标准
 */
func bubbleSort(_ nums: inout [Int]) {
    if nums.count < 2 { return }
    for i in 0..<nums.count { // 总共需要对比的次数
        for j in 0..<nums.count - i - 1 { // 每一次最后一个数必定已经排序为最大
            if nums[j] > nums[j + 1] {
                // 使用元祖交换值
                nums.swapAt(j, j + 1)
            }
        }
    }
}

/*
 冒泡排序优化：在某次排序后如果已经都排序好了，则退出后续的循环
 */
func bubbleSort2(_ nums: inout [Int]) {
    if nums.count < 2 { return }
    var sorted = true
    for i in 0..<nums.count {
        sorted = true
        for j in 0..<nums.count - i - 1 {
            if nums[j] > nums[j + 1] {
                nums.swapAt(j, j + 1)
                sorted = false
            }
        }
        if sorted { break }
    }
}

/*
 冒泡排序优化：记录后半部分排序好的位置，避免重复排序已经排序的部分
 */
func bubbleSort3(_ nums: inout [Int]) {
    if nums.count < 2 { return }
    var sorted = true
    var index = nums.count - 1
    for _ in 0..<nums.count {
        sorted = true
        for j in 0..<index {
            if nums[j] > nums[j + 1] {
                nums.swapAt(j, j + 1)
                sorted = false
                index = j
            }
        }
        if sorted { break }
    }
}

/*
 冒泡排序优化：缩小两边的边界，并记录是否已完成排序
 */
func bubbleSort4(_ nums: inout [Int]) {
    if nums.count < 2 { return }
    var sorted = true
    var left = 0
    var right = nums.count - 1
    // 因为从两端双向排序，左边每次都会是最小，右边每次都是最大，排完的次数刚好到中间位置，
    // 不需要nums.count的次数那么多，写nums.count也没问题，因为会提前退出
    for _ in 0..<nums.count / 2 {
        sorted = true
        for j in left..<right {
            if nums[j] > nums[j + 1] {
                nums.swapAt(j, j + 1)
                sorted = false
                right = j
            }
        }
        if sorted { break }
        
        sorted = true
        
        for j in (left + 1...right).reversed() {
            if nums[j] < nums[j - 1] {
                nums.swapAt(j, j - 1)
                sorted = false
                left = j
            }
        }
        if sorted { break }
    }
}

/*
 插入排序：O(n^2)
 */
func insertSort(_ array: inout [Int]) {
    // 从1开始遍历，默认不清楚数组是否部分有序
    for i in 1..<array.count {
        // 取出第i位元素 赋给临时变量 做后续比较
        let tmp = array[i]
        var j = i - 1
        // 当比到最左边或临时变量tmp小于比较的元素时
        while j>=0 && tmp < array[j] {
            // 比较的元素array[j]，向右移动一位
            array[j + 1] = array[j]
            // j-1，并继续和左边元素比较
            j -= 1
        }
        // 临时变量tmp放到已排序好的数组的下一位
        array[j + 1] = tmp
    }
}

/*
 选择排序：O(n^2)，交换次数少于冒泡
 */
func selectSort(_ nums: inout [Int]) {
    for i in 0..<nums.count {
        var k = i
        for j in (i + 1)..<nums.count {
            if nums[j] < nums[k] {
                k = j
            }
        }
        
        if i != k {
            nums.swapAt(i, k)
        }
    }
}

/*
 堆排序：O(nlogn)
 */
func heapSort(_ array: inout [Int]) {
    
    //构建大顶堆 从最后一个非叶子结点倒序遍历
    for i in (0...(array.count / 2 - 1)).reversed() {
        //从第一个非叶子结点从下至上，从右至左调整结构
        adjustHeap(&array, i, array.count)
    }
    //上面已将输入数组调整成堆结构
    for j in (1...(array.count - 1)).reversed() {
        //堆顶元素与末尾元素进行交换
        array.swapAt(0, j)
        adjustHeap(&array, 0, j)
    }
}

/*
 调整堆结构
 */
func adjustHeap(_ array: inout [Int],_ i: Int,_ length: Int) {
    var j = i
    //取出当前元素i
    let tmp = array[j]
    var k = 2 * i + 1
    while k < length {
        //左子节点小于右子节点
        if(k + 1 < length && array[k] < array[k + 1]) {
            //取到右子节点下标
            k += 1
        }
        if(array[k] > tmp){
            //如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
            array[j] = array[k]
            j = k
        } else {
            break
        }
        k = k * 2 + 1
    }
    //将tmp值放到最终的位置
    array[j] = tmp
}

/** 标准的快排 */
func quickSort(_ array: inout [Int], _ l: Int,_ r: Int) {
    if l >= r { return }
    
    var left = l
    var right = r
    let key = array[left]
    while left < right {
        while left < right && array[right] > key {
            right -= 1
        }
        array[left] = array[right]
        while left < right && array[left] < key {
            left += 1
        }
        array[right] = array[left]
    }
    array[left] = key
    quickSort(&array, l, left - 1)
    quickSort(&array, left + 1, r)
}

/** 快排: 利用二分查找思路进行快速排序，需要额外空间得到左右两边数据 */
func quickSort2(_ array: [Int]) -> [Int] {
    guard array.count > 1 else {
        return array
    }
    let num = array[array.count / 2]
    let left = array.filter { $0 < num }
    let mid = array.filter { $0 == num }
    let right = array.filter { $0 > num }
    return quickSort2(left) + mid + quickSort2(right)
}

/** 归并排序 */
func mergeSort(_ array: inout [Int]) {
    var helper = [Int].init(repeating: 0, count: array.count)
    slipSort(&array, 0, array.count - 1, &helper)
}

func slipSort(_ array: inout [Int], _ l: Int,_ r: Int,_ helper: inout [Int]) {
    if l >= r { return }
    
    let mid = (r - l) / 2 + l
    slipSort(&array, l, mid, &helper)
    slipSort(&array, mid + 1, r, &helper)
    mergeSliped(&array, l, mid, r, &helper)
}

func mergeSliped(_ array: inout [Int], _ l: Int,_ mid: Int,_ r: Int, _ helper: inout [Int]) {
    var l = l
    var m = mid
    var index = 0
    while l < m && m <= r {
        if array[l] < array[mid] {
            helper[index] = array[l]
            l += 1
        } else {
            helper[index] = array[m]
            m += 1
        }
        index += 1
    }
    
    while l < m {
        
    }
}