kotlin 版本的归并排序

借鉴了其他语言的实现方法，结合和kotlin的一些特性和语法糖，产出具有kotlin特色的归并排序算法实现。如果有语法相关的问题也可以问我。

fun sort(array: IntArray, start: Int = 0, end: Int = array.size - 1) {
    if (start >= end) return
    println("sort  start = $start, end = $end")
    if ((end - start + 1) != 2) {
        // 区间的元素 > 2
        val mid = (start + end) / 2
        // 递归
        sort(array, start, mid)
        sort(array, mid + 1, end)
        merge(array, start, mid, end)
    } else {
        // 仅有两个元素的区间，比较大小并交换
        if (array[start] > array[end]) {
            array[start] = array[end].also { array[end] = array[start] }
        }
    }
}

// 合并数组
fun merge(array: IntArray, start: Int, mid: Int, end: Int) {
    println("merge start = $start, mid = $mid, end = $end")
    for (i in start..end) {
        println("merge enter array[$i] = ${array[i]}")
    }
    val t1 = array.takeRange(start, mid)
//    println("t1")
//    t1.forEach(::println)
    val t2 = array.takeRange(mid + 1, end)
//    println("t2")
//    t2.forEach(::println)
    var index1 = 0
    var index2 = 0
    var arrayIndex = start
    while (index1 != t1.size && index2 != t2.size) {
        if (t1[index1] >= t2[index2]) {
            println("merge while t1[index1] >= t2[index2], t1[${index1}] = ${t1[index1]}, t2[${index2}] = ${t2[index2]}")
            array[arrayIndex++] = t2[index2++]
        } else {
            println("merge while t1[index1] <  t2[index2], t1[${index1}] = ${t1[index1]}, t2[${index2}] = ${t2[index2]}")
            array[arrayIndex++] = t1[index1++]
        }
    }
    // 修正如果两个数组大小相同的情况下出现的问题
    if (t1.size == t2.size) {
        array[arrayIndex] = max(t1[t1.size - 1], t2[t2.size - 1])
    }
    // 两个数组大小不一致的时候，部分数据没merge
    if (index1 != t1.size - 1) {
        for (i in index1 until t1.size) {
            array[arrayIndex++] = t1[i]
        }
    }
    if (index2 != t2.size - 1) {
        for (i in index2 until t2.size) {
            array[arrayIndex++] = t2[i]
        }
    }
    for (i in start..end) {
        println("merge out   array[$i] = ${array[i]}")
    }
}

// 取出数组的某个区间
fun IntArray.takeRange(start: Int, end: Int): IntArray {
    val size = end - start + 1
    val res = IntArray(size)
    for (i in 0 until size) {
        res[i] = this[i + start]
    }
    return res
}

fun main() {
    val arr = intArrayOf(35, 24, 61, 232, 48, 79, 121, 29, 69, 49)
    sort(arr)
    arr.forEach(::println)
}
复制代码

转载请注明出处