归并排序的核心是把两个有序数组合并为一个新的有序数组,具体操作就是通过递归的方式层层执行核心方法。
fun mergeSort(array: IntArray): IntArray {
//嵌套函数
fun merge(left: IntArray, right: IntArray): IntArray {
val ret = IntArray(left.size + right.size)
var i = 0
var p = 0
var q = 0
while (p < left.size && q < right.size) {
if (left[p] <= right[q]) {
ret[i++] = left[p++]
} else {
ret[i++] = right[q++]
}
}
if (p == left.size) {
for (index in q until right.size) {
ret[i++] = right[index]
}
} else {
for (index in p until left.size) {
ret[i++] = left[index]
}
}
return ret
}
if (array.size < 2)
return array
val middle = array.size / 2
val left = array.copyOfRange(0,middle)
val right = array.copyOfRange(middle,array.size)
return merge(mergeSort(left), mergeSort(right))
}
kotlin小白，有错误请不吝指教~
