酷! kotlin 的一行快排实现

前言

之所以研究怎么用 kotlin 实现一行代码快排,主要是之前学 python 时遇到过,觉得很酷,所以最近就在想 kotlin 同样有着丰富的库函数以及各种语法糖,那么在不考虑效率的情况下 kotlin 有没有办法做到同样的效果呢?

分析

其实在 Quick Sort 一个很重要的部分就是一个分隔操作(partition),以第一个数为界,将整个数组分成 2 个部分,然后依次递归这个过程,如果当前数组的大小小于等于 1 的话,那么就没必要继续进行分隔了。这就是二路快排的思路简述。如果你不太了解快速排序,建议还是先去简单了解下

所以这里的关键就是 kotlin 有没有一个高阶函数能够将数组分成两个部分。很巧的就是,kotlin 中正好就有个 partition 函数,函数原型如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* Splits the original collection into pair of lists,
* where *first* list contains elements for which [predicate] yielded `true`,
* while *second* list contains elements for which [predicate] yielded `false`.
*/
public inline fun <T> Iterable<T>.partition(predicate: (T) -> Boolean): Pair<List<T>, List<T>> {
val first = ArrayList<T>()
val second = ArrayList<T>()
for (element in this) {
if (predicate(element)) {
first.add(element)
} else {
second.add(element)
}
}
return Pair(first, second)
}

源码可以说是很直观了,根据传入的表达式进行分类,用两个集合分别保存符合表达式的数据和不符合表达式的数据,然后返回两个集合 Pair

根据这个 partition 函数,我们的实现思路就很明确了

每次递归:
    如果数组或集合长度小于等于 1:
        返回这个数组或集合
    否则:
        以第一个元素为界,将所有元素分成两部分;
        对两个部分继续递归;
        拼接两个部分以及第一个元素;
        返回拼接结果;

Show you my code

上面简单分析了下思路,不过我觉得看着思路也是很模糊的,不如直接来看代码的实在,毕竟 talk is cheap

根据上面的伪码,可以把代码写成下面的样子

1
2
3
4
5
6
7
8
fun quickSort(list: List<Int>): List<Int> {
return if (list.size <= 1) list
else {
list.takeLast(list.lastIndex)
.partition { it < list[0] }
.run { quickSort(first) + list[0] + quickSort(second) }
}
}

可是上面的代码用了七行呀!?说好的一行呢???

emmmmmmm,其实这里写成这样主要是为了方便看,我们还没用到 kotlin 其他的语法糖呢

在 kotlin 如果 if-else 都有返回值的话,我们可以把 return 写在最前面,上面的代码也看到了。其次,我们的 else 语句其实就只有一行,只是链式调用分开写了而已。那么这么看整个方法体也只有一行,所以我们连 return 和方法体的花括号都可以省掉,直接将方法体接在方法后即可。所以最终版本应该是下面这个样子

1
fun quickSort(list: List<Int>): List<Int> = if (list.size <= 1) list else list.takeLast(list.lastIndex).partition { it < list[0] }.run { quickSort(first) + list[0] + quickSort(second) }

是不是很酷?虽然这样写的实际意义不大,存粹是为了好玩😃。但是这也体现了语法糖的强大,能为我们节省很多代码,并且 kotlin 的灵活也让我们有了更多的想法。

文章作者: Inno Fang
文章链接: https://innofang.github.io/2018/02/27/酷! kotlin-的一行快排实现/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来自 Inno's Blog